关于javascript:深入分析数组去重

数组去重 是常见的面试考点，所以我就试着深刻学习一下。网上也有很多数组去重的文章，但我本人感觉剖析地不够深刻，其实其中很多的实现都是反复的，能够归为一类，比方 双重循环法 和 indexOf 法 的实质都是双重循环，故写下此文，做进一步的总结，同时加深了解。

1. 双重循环

这种办法就很间接，很好了解。那就是创立一个新的空数组，每次咱们会从原数组中取出一个元素，拿它和新数组的元素进行一一比拟。如果在新数组没发现和取出元素相等的元素，就将其放入这个新数组中；如果发现有和取出元素相等的元素，不放入新数组中。当原数组中的数组全都取出来时，这个新数组就是去重后的所有数据了。

这种数组去重的实现的工夫复杂度是 O(n^2)。

const unique = arr => {let res = [];
    for (let i = 0, len = arr.length; i < len; i++) {
        let j = 0, len2 = res.length;
        for (; j < len2; j++) {if (arr[i] === res[j]) break;
        }
        if (j == len2) res.push(arr[i]);  // j == len2 示意没有执行 break。}
    return res;
}

当然这里的第一个循环能够改为 forEach() 办法，第二个 for 循环能够改为应用 includes() 或者 indexOf() 办法，工夫复杂度没什么变动，不过代码更简洁。

const unique = arr => {let res = [];
    arr.forEach(item => {if (!res.includes(item)) res.push(item); 
    })
    return res;
} 

2. 查找元素第一次呈现的地位

从后往前遍历数组，检测元素第一次呈现的地位是否为以后元素的地位。如果不是，阐明有反复，移除以后元素；如果没有，就不移除。

之所以从后往前遍历，是因为咱们要搬移元素（其实就是 splice）。当然你也能够抉择从前往后遍历，不过这样的话，如果遍历时以后元素被移除了，那么移除元素后的 arr[i] 对应的元素其实是原来 arr[i+1]，因而此时 i 不能自增，且完结的条件要改为 i == len-1，就很麻烦。

这种写法不须要创立新的数组，空间复杂度为 O(1)。

const unique = arr => {for (let i = arr.length - 1; i >= 0; i--) {for (let j = 0; j < i; j++) {if (arr[j] === arr[i]) arr.splice(i, 1);
        }
    }
    return arr;
}

这里的代码实现是尽量减少工夫复杂度的。说个题外话，其实下面这里还能够再优化一下，因为咱们这里的元素搬移并不是一次性搬移到最终的地位上的。优化思路是先标记要所有要删除的元素索引，而后从前往后遍历数组，每遇到第 m 个删除索引，前面的元素就笼罩掉它们往前第 m 位的数组元素，这里就不实现了，也就轻易提一下。

如果改为配合应用 filter() 和 includes() 办法的话，咱们能够让代码可读性更好一些（性能会略微降落，因为 incluedes 会遍历整个数组），具体实现就不写了。

3. 排序后去重

排序算法有很多种，咱们就用 js 自带的排序算法吧。顺带一说，v8 引擎 的 sort() 办法在数组长度小于等于 10 的状况下，会应用插入排序，大于 10 的状况下会应用疾速排序。

排（guai）好（guai）序（zhanhao）后，查看前后两个相邻元素，如果以后元素和后面的元素不相等，才将以后元素放入新数组中。

const unique = arr => {if (arr.length < 2) return arr; 
    arr.sort();
    let r = [arr[0]];
    for (let i = 1, len = arr.length; i < len; i++) {if (a[i] !== a[i - 1]) r.push(a[i]);
    }
    return r;
}

这种去重局限性十分大。它不适用于对象，因为对象不适宜进行排序。sort() 的默认排序程序是依据字符串 Unicode 码点进行排序，貌似会把对象转为字符串再进行排序，个别的对象都会转为 “[object Object]”，无奈保障两个援用同一个对象的变量能相邻排列。

4. 应用散列表

散列表，在 JavaScript 中是通过对象来实现的。散列表的长处是，个别状况下读取数据的工夫复杂度是 O(1)。但 js 的对象的键只能为字符串类型，不过能够思考应用 ES6 新增的 Map 数据结构，它容许应用任何类型的值作为键。

上面的实现应用的是一般对象作为散列表，有很大的局限性，无奈对 js 对象 进行去重（对象都会转为相似 [object Object] 的字符串）。另外，对于 js 对象来说，a[‘1’] 和 a[1] 是相等的，因为 1 会转换为 ’1’，这样就无奈分辨出 1 和 ‘1’，从而谬误地在去重过程中抛弃其中的一个元素，所以我做了简略地改进，键名应用的不是 arr[i] 而是 typeof(arr[i]) + arr[i]。

const unique = arr => {let r = [];
    let map = {};
    for (let i = 0, len = arr.length; i < len; i++) {const item = arr[i];
        if (!map[typeof(item) + item]) {r.push(arr[i]);
        }
        map[typeof(item) + item] = true; 
    }
    return r;
} 

这种实现形式，工夫复杂度能够达到 O(n)。

如果思考对象也能去重，能够思考应用 ES6 的 Map。

5. ES6 的 Set

ES6 提供了新的数据结构。Set 实例会认为两个 NaN 是相等的（只管 NaN !== NaN），并认为两个对象是不等的（当然这里两个对象的意思，示意的是两个指向不同内存空间的援用类型变量）。

并不太理解 Set 的源码实现，就不剖析性能了。

const unique = arr => {return Array.from(new Set(arr))
}

十分简洁，如果你的运行环境反对 ES6，或者能够编译成 ES5，我很举荐应用这个去重计划。

思考 NaN 的去重

如果要思考 NaN 的去重，就须要略微对代码进行一些批改。

简略来说就是，判断 item 是否为 NaN，而后查看返回的数组中是否已有 NaN。如果有，放入数组；否则不放入。

const unique = arr => {let res = [];
    let hasNaN = false;
    arr.forEach(item => {if(!hasNaN && Number.isNaN(item)) {res.push(item);
            hasNaN = true
        }else if (!res.includes(item)) {res.push(item); 
        }
    })
    return res;
} 

lodash 如何实现去重

简略说下 lodash 的 uniq 办法的源码实现。

这个办法的行为和应用 Set 进行去重的后果统一。

当数组长度大于等于 200 时，会创立 Set 并将 Set 转换为数组来进行去重（Set 不存在状况的实现不做剖析）。当数组长度小于 200 时，会应用相似后面提到的 双重循环 的去重计划，另外还会做 NaN 的去重。

总结

一般来说，在开发中，要进行去重的数组并不是很大，不用太思考性能问题。所以在工程中，为了不把简略的问题复杂化中，倡议应用最简洁的 ES6 的 Set 转数组的计划来实现。当然具体问题具体分析，要依据场景抉择真正适合的去重计划。

另外，其实“相等”有很多种定义，ES6 中就有四种相等算法，这里就不多说了，有趣味的话能够看看这篇文章：JavaScript 中的相等性判断。仍旧是依据场景抉择适合的相等算法。

参考

• 掘金 –7 种办法实现数组去重
• JavaScript 专题之数组去重
• lodash 的 uniq 办法实现
• JavaScript 中的相等性判断