Six Methods to Deduplicate JavaScript Array

Method 1

Without thinking, we can get a solution to the complexity of O (n ^ 2). Define a variable array res to save the results, traverse the array that needs to be duplicated. If the element already exists in res, it is a duplicate element. If not, it is put into res.

 function unique(a) {
 var res = [];
 for (var i = 0, len = a.length; i < len; i++) {
 var item = a[i];
 for (var j = 0, jLen = res.length; j < jLen; j++) {
 if (res[j] === item)
 break;
 }
 if (j === jLen)
 res.push(item);
 }
 return res;
}
var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]

The code is very simple, so can it be simpler? If browser compatibility is not considered, we can use the Array. prototype. indexOf method provided by ES 5 to simplify the code.

function unique(a) {
 var res = [];
 for (var i = 0, len = a.length; i < len; i++) {
 var item = a[i];
 (res.indexOf(item) === -1) && res.push(item);
 }
 return res;
}
var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]

Since indexOf is used, filter may be added.

function unique(a) {
 var res = a.filter(function(item, index, array) {
 return array.indexOf(item) === index;
 });
 return res;
}
var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]

Method 2

Method 1 compares the elements in the original array with element 11 in the result array. We can change our thinking and put the last element of the repeating elements in the original array into the result array.

function unique(a) {
 var res = a.filter(function(item, index, array) {
 return array.indexOf(item) === index;
 });
 return res;
}
var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]

Although the complexity is still O (n ^ 2), you can see that the result is different, and 1 appears at the back of the array, because the result array takes the last occurrence of the element.

Method 3 (sort)

If only the above O (n ^ 2) scheme is answered in the written interview, it may not satisfy the interviewer. Here are some advanced schemes.

After the array is sorted with sort, theoretically the same elements will be placed in adjacent positions, so it is enough to compare the elements before and after.

function unique(a) {
 return a.concat().sort().filter(function(item, pos, ary) {
 return !pos || item != ary[pos - 1];
 });
}
var a = [1, 1, 3, 2, 1, 2, 4];
var ans = unique(a);
console.log(ans); // => [1, 2, 3, 4]

But here's the problem again. 1 and "1" will be ranked as 1, and different Object will be ranked as 1, because they have the same result as toString (), so this error will occur:

function unique(a) {
 return a.concat().sort().filter(function(item, pos, ary) {
 return !pos || item != ary[pos - 1];
 });
}
var a = [1, 1, 3, 2, 1, 2, 4, '1'];
var ans = unique(a);
console.log(ans); // => [1, 2, 3, 4]

Of course, you can write this comparison function for different types that may appear in the array. But it seems a little troublesome.

Method 4 (object)

Use JavaScript Object object as a hash table, which is also a written test a few years ago when the solution, with sort 1, can be duplicated completely by Number basic type composition of the array.

function unique(a) {
 var seen = {};
 return a.filter(function(item) {
 return seen.hasOwnProperty(item) ? false : (seen[item] = true);
 });
}
var a = [1, 1, 3, 2, 1, 2, 4];
var ans = unique(a);
console.log(ans); // => [1, 3, 2, 4]

It's still the same problem as method 31, because the key values of Object are all String types, so there is no distinction between 1 and "1". We can make a slight improvement and store the types in key as well.

function unique(a) {
 var ret = [];
 var hash = {};
 for (var i = 0, len = a.length; i < len; i++) {
 var item = a[i];
 var key = typeof(item) + item;
 if (hash[key] !== 1) {
 ret.push(item);
 hash[key] = 1;
 }
 }
 return ret;
}
var a = [1, 1, 3, 2, '4', 1, 2, 4, '1'];
var ans = unique(a);
console.log(ans); // => [1, 3, 2, "4", 4, "1"]

Although it solves the annoying 1 and "1" problems, there are other problems!

function unique(a) {
 var ret = [];
 var hash = {};
 for (var i = 0, len = a.length; i < len; i++) {
 var item = a[i];
 var key = typeof(item) + item;
 if (hash[key] !== 1) {
 ret.push(item);
 hash[key] = 1;
 }
 }
 return ret;
}
var a = [{name: "hanzichi"}, {age: 30}, new String(1), new Number(1)];
var ans = unique(a);
console.log(ans); // => [Object, String]

However, if the array elements are all Number values of the underlying type, the key-value alignment method should be the most efficient!

Method 5 (ES6)

ES6 deploys Set and Array. from methods, so powerful! If the browser supports it, it can be like this:

function unique(a) {
 return Array.from(new Set(a));
}
var a = [{name: "hanzichi"}, {age: 30}, new String(1), new Number(1)];
var ans = unique(a);
console.log(ans); // => [Object, Object, String, Number]

_.unique

Finally, let's look at how underscore implements this. underscore encapsulates this in the _. unique method, which is called _. unique (array, [isSorted], [iteratee]). Among them, the first parameter is necessary, which is an array that needs to be deduplicated, the second parameter is optional, if the array is ordered, the Boolean value true can be passed in, and the third parameter is optional, if the result of array iteration needs to be deduplicated, an iterative function can be passed in. The de-duplication of array elements is based on the === operator.

In fact, it is very simple. The implementation in underscore is similar to Method 1 above.

Let's look at its core code:

function unique(a) {
 var res = [];
 for (var i = 0, len = a.length; i < len; i++) {
 var item = a[i];
 (res.indexOf(item) === -1) && res.push(item);
 }
 return res;
}
var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans); // => [1, "1", "2"]

0

The outer loop traverses the array elements. For each element, if the array is ordered, it is compared with the previous element. If it is the same, it has already appeared and is not added to the result array. Otherwise, it is added. If there is an iterative function, calculate the value passed into the iterative function, de-duplicate the value, and call the. contains method. The core of this method is to call the. indexOf method, which is similar to the method 1 mentioned above.