Javascript数组去重

偶然和同事谈到面试的Javascript问题，其中基本上都会有一道问题就是数组去重，随着对于语言深入的学习，这道基础问题也有了更多的解法。

理解问题

该问题要注意

• 两个元素通过===比较，返回true则视为相同元素，需要去重，在此基础下，1和'1'是不同元素，1和new Number(1)是不同元素，{}和{}是不同元素（引用不同）

基本解法

方法一：遍历数组，若存在于数组，则说明是重复元素，将没有的元素放入新数组

function unique(arr) {
    var newArr = [];
    for (var i = 0, len = arr.length; i < len; i ++) {
        var item = arr[i];
        for (var k = 0, kLen = newArr.length; k < kLen; k ++) {
            if (newArr[k] === item) break;
        }
        if (k === kLen) newArr.push(item);
    }

    return newArr;
}

此方法复杂度为O(n^2)，逻辑非常简单，大概的思路也如此。

进阶一下，使用indexOf方法简化

具体可以看看Javascript中的Array.prototype.indexOf()方法：

function unique(arr) {
    var newArr = [];
    for (var i = 0, len = arr.length; i < len; i ++) {
        var item = arr[i];
        (newArr.indexOf(item) === -1) && newArr.push(item);
    }
    return newArr;
}

其中(newArr.indexOf(item) === -1) && newArr.push(item)这种写法不太常见，这里也做个记录

&& operator
Logical And
Usage: expr1 && expr2
Description:
Returns expr1 if it can be converted to false; otherwise, returns expr2.
Thus, when used with Boolean values, && returns true if both operands are true; otherwise, returns false.
--- MDN

即:

if (newArr.indexOf(item) === -1) newArr.push(item)

加入filter()方法

具体方法查阅Array.prototype.filter()

function unique(arr) {
    var newArr = arr.filter(function(item, index, array){
      return array.indexOf(item) === index;
    }) 
        
    return newArr;
}

// ES6写法
const unique = (arr) => arr.filter((item, index, arr) => array.indexOf(item) === index)

简洁的多，当然这种写法考验jser对于数组相关方法的熟悉程度。

进阶解法

当考虑到算法复杂度的层面时，以上解法就显得有些平庸了，这里我们考虑几种进阶的方案。

拥抱ES6，使用Set和Array.from

Set对象见这里

Array.from()方法见这里

可以看到，Set是ES6中内置的一个对象，是一些值的集合，可以遍历循环其中元素的插入顺序，在Set中的值可能只出现一次，在集合中是独一无二的。

而Array.from()则是ES6新增的数组方法，他允许你基于array-like objects(objects with a length property and indexed elements)或者iterable obejcts(objects where you can get its elements such as Map and Set去创建一个数组。

基于以上两个方法，我们可以这样写：

function unique(arr) {
    return Array.from(new Set(arr));    // return an array created by Set
}

---

以上方法针对的都是原始变量，当元素为Object类型时要作何处理呢

console.log(1 === 1) // true
console.log('1' === '1')  // true
console.log({a: 1} === {a: 1})  //false

可以看出，{a: 1} === {a: 1}为false，这是因为对象存储的是引用，而原始变量存储的则是值

因此我们需要换一个思路去实现。

使用HashTable(哈希表)

HashTable在Javascript中是一个简单的Object，他的Key永远是String类型，因此我们不能区分字符串和数字表示的相同的值，如1和'1'

var hashTable = {};
hashTable[1] = true;
hashTable['1'] = true;
console.log(hashTable);
// {'1': true}

那么如果要区分开来，我们需要将Key变为唯一的，使用JSON.stringify:

var hashTable = {};
hashTable[JSON.stringify(1)] = true;
hashTable[JSON.stringify('1')] = true;
console.log(hashTable);  // {'1': true, '"1"': true}

综上，我们实现对于任何类型元素进行去重的方法：

function unique(arr) {
    var hashTable = {};

    return arr.filter(function(item) {
        var key = JSON.stringify(item);
        var match = Boolean(hashTable[key]);

        return (match ? false: hashTable[key] = true);
        })
}

阅读材料：

Array.prototype.indexOf()
Array.prototype.filter()
Set
Array.from()
JSON.stringify()
Arrow functions