3

If i've got an array like the following as an example:

myArray = [1,4,5,1,5];

How would I remove all the duplicate values (all the 1's and 5's in this example) and only return the unique elements (4 in this example).

Any help would be greatly appreciated.

E7AD
  • 67
  • 8

4 Answers4

4

I think

[1,4,5,1,5].filter(function(x, n, self) { 
    return self.indexOf(x) == self.lastIndexOf(x) 
})

A probably more efficient hash-based version using underscore:

a =[1, 2, 3, 3, 4, 2, 1, 5]
uniqs = _.chain(a).countBy().pairs().filter(function(x) {
    return x[1] == 1
}).pluck(0).value()

or plain javascript:

a = [1, 2, 3, 3, 4, 2, 1, 5]
hash = {}

a.forEach(function(x) {
    hash[x] = (Number(hash[x]) || 0) + 1
});

uniq = Object.keys(hash).filter(function(n) {
    return hash[n] == 1
});

Note however, that this would convert array values to strings (the result will be ["4","5"]).

If you're happy with the array being sorted, you can also do it like this:

a = [1, 2, 3, 3, 4, 2, 1, 5]

uniq = a.sort().filter(function(x, n, self) {
    return x != self[n - 1] && x != self[n + 1];
});

//[4, 5]

The second and third methods have a serious limitation that they only work with primitive values - you cannot "uniquify" an array of objects. The first function works just fine:

x = {x:1}; y = {y:1}; a = [x, y, x, x];
uniq = a.filter(function(x, n, self) { 
    return self.indexOf(x) == self.lastIndexOf(x) 
})
// {"y":1}

For those curious, performance tests (quite inconsistent in different browsers): http://jsperf.com/efficient-unique/2

georg
  • 211,518
  • 52
  • 313
  • 390
2

This works, and is far more efficient that a naive search (O(nlog(n)) rather than O(n^2)), however it does modify the existing array.

var unique = [];

myArray.sort();

for (var i=0, j;i<myArray.length;i = j) {
    for (j=i+1;j<myArray.length && myArray[i] === myArray[j]; j++);

    if (j == i + 1) {
        unique.push(myArray[i]);
    }
}

// use unique

As discussed in the comments, you can also utilize an object and achieve an O(n) solution, however the execution time of this approach varies wildly across platforms (sometimes being slower than the above solution, and other times being quicker).

var unique = [], hash = {}, curr;

for (var i=0;i<myArray.length;i++) {
    curr = myArray[i];

    hash[curr] = (Number(hash[curr]) || 0) + 1;
}

for (var x in hash) {
    if (hash[x] === 1) {
        unique.push(x);
    }
}

// use unique
Matt
  • 74,352
  • 26
  • 153
  • 180
  • 1
    Have you got any proof for "far more efficient"? – georg Aug 21 '13 at 21:07
  • I haven't done a jsperf, if that's what you mean, but like I said, this is an `O(nlog(n))` algorithm, rather than the `O(n^2)` that a naive algorithm would be. – Matt Aug 21 '13 at 21:09
  • 1
    @thg435: Here's a jsPerf to satisfy your curiosity; http://jsperf.com/efficient-unique. It's not *that* more efficient at with such a small array, but the gain will obviously grow as `n` does. – Matt Aug 21 '13 at 21:16
  • 1
    @Matt: so, "far more efficient" is obviously incorrect. I'd suggest you update the post to reflect that (and skip the big-O stuff, which is wrong either). – georg Aug 21 '13 at 21:20
  • 1
    @thg435: The two tests you ran (assuming it's you) show my algorithm is twice as quick as the naive approach (1,900,000 vs 900,000ops/sec). How is that not "far more efficient", even at such a small array? Care to explain how my big-O notation is wrong? – Matt Aug 21 '13 at 21:22
  • 1
    @Matt: Big O describes how the function grows, not how "fast" it is. In this particular case, all this "efficient" and "big O" talk do nothing but confuse people. For arrays < 10,000 items there will be no practical difference between two methods. – georg Aug 21 '13 at 21:38
  • I think you're being too pedantic here. The statement in my answer about my algorithm being `O(nlog(n))` and a naive one being `O(n^2)` is correct. My statement about it being far more efficient is true both in growth terms, and in terms of speed, as shown by the jsperf. I'm not sure what more you want. If the talk confuses people they can read up on it or ignore it; it still stands. Of course all "speed" talk will be relative to the speed of processors; what else would you expect? – Matt Aug 21 '13 at 21:49
  • 1
    @Matt: In context of javascript, the speed talk rarely makes sense. In this particular case it's especially pointless, because if you really need speed, the problem can be trivially solved using hash tables in linear time. Have you tested that? – georg Aug 21 '13 at 22:01
  • 1
    http://jsperf.com/efficient-unique/2: the proposed "efficient" function fails miserably against a hash-based solution. – georg Aug 21 '13 at 23:47
  • @thg435: I proposed it as *more* efficient than the naive approach, which, no-matter how many tests you continue to throw at it, remains the case. You are correct about a linear time solution; I did not consider it when writing the answer, and will update accordingly; although its interesting how the execution time of that solution varies so wildly across platforms! – Matt Aug 22 '13 at 11:32
1

Try this:-

var arr = [1,4,5,1,5];
var sorted_arr = arr.sort(); 
var results = [];
for (var i = 0; i < arr.length - 1; i++) {
    if (sorted_arr[i + 1] !== sorted_arr[i]) {
        results.push(sorted_arr[i]);
    }
}
Rahul Tripathi
  • 168,305
  • 31
  • 280
  • 331
  • This is not what the OP wants. – Matt Aug 21 '13 at 20:59
  • 1
    That still doesn't do what the OP asks. – Matt Aug 21 '13 at 21:04
  • @Matt:- Got that. Updated my answer!! Please do correct me if that doesnt work!! – Rahul Tripathi Aug 21 '13 at 21:08
  • 1
    You probably want to `push()` if the next element `!==` the current element, rather than if it `===`. This will also fail if there are more than 2 occurences of an element in the array (e.g. `[1,1,1,2]`). – Matt Aug 21 '13 at 21:14
  • You mean to say I should write if (sorted_arr[i + 1] !== sorted_arr[i]) { results.push(sorted_arr[i]); instead of if (sorted_arr[i + 1] == sorted_arr[i]) { results.push(sorted_arr[i]);??? – Rahul Tripathi Aug 21 '13 at 21:16
  • Yes, you can see this for yourself; http://jsfiddle.net/mpQAz/. The output should be `[4]`. You're getting `[1,5]`. – Matt Aug 21 '13 at 21:17
  • 1
    It's not my downvote. If you fix the problem where "This will also fail if there are more than 2 occurences of an element in the array (e.g. [1,1,1,2]).", I'll give you an upvote though. – Matt Aug 21 '13 at 21:26
0

You could try using this jquery function: http://api.jquery.com/jQuery.unique/

"The $.unique() function searches through an array of objects, sorting the array, and removing any duplicate nodes."

  • 2
    `jQuery.unique` is for DOMNodes, per the documentation. "Sorts an array of DOM elements". – Matt Aug 21 '13 at 20:52