阅读 2532

20多种数组去重?看懂这4种,全都不在话下

为什么写这篇文章

在掘金上每过一段时间就会出现一次题材相似的讨论,例如面试,手写函数,而此题材也不例外——数组去重。我看到过论坛上出现过的一次次的数组去重的文章,但是个人觉得可能都不太完善,所以,我期望尝试对 JS 数组去重进行一次 “系统性” 的总结。

资料

前提

测试用例

该用例包含了所有简单基本类型以及对象,基本可以涵盖所有常见数据的可能

let a = {};
let b = { a: 1 };
let testArr = [1, 1, "1", "1", "a", "a", {}, {}, { a: 1 }, a, a, b, [], [], [1], undefined, undefined, null, null, NaN, NaN];
复制代码

去重标准

以下的代码以 lodash 中默认去重函数的去重结果为标准,lodash uniq 函数去重结果如下

// lodash@4.17.15
_.uniq(testArr);
// [1, "1", "a", {}, {}, { a: 1 }, {}, { a: 1 }, [], [], [1], undefined, null, NaN];
复制代码

去重 4 大类型

对于 JS 数组去重来说,其实万变不离其中,我简单的总结了以下 4 种去重类型,而围绕着各种类型,由于 JS 丰富的函数以及工具能力,可以有多种实现方法,不管是采用 forEach,reduce,filter 等来循环并拼装新数组,还是用最基础的 for 循环以及 push 来循环并组装新数组,暂时都可以归纳到以下的 4 个类型

数组元素比较型

该方法是将数组的值取出与其他值比较并修改数组

双层 for 循环

取出一个元素,将其与其后所有元素比较,若在其后发现相等元素,则将后者删掉

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

// 运行结果
// [1, "1", "a", {}, {}, { a: 1 }, {}, { a: 1 }, [], [], [1], undefined, null, NaN, NaN]
// 与 lodash 结果相比 NaN 没有去掉
复制代码

由于 NaN === NaN 等于 false,所以重复的 NaN 并没有被去掉

排序并进行相邻比较

先对数组内元素进行排序,再对数组内相邻的元素两两之间进行比较,经测试,该方法受限于 sort 的排序能力,所以若数组不存在比较复杂的对象(复杂对象难以排序),则可尝试此方法

function uniq(arr) {
    arr.sort();
    for (let i = 0; i < arr.length - 1; i++) {
        arr[i] === arr[i + 1] && arr.splice(i + 1, 1) && i--;
    }
    return arr;
}
// 运行结果
//[[], [], 1, "1", [1], NaN, NaN, {}, {}, { a: 1 }, {}, { a: 1 }, "a", null, undefined];
// 与 lodash 结果相比 NaN 没有去掉,且对象的去重出现问题
复制代码

同样由于 NaN === NaN 等于 false,所以重复的 NaN 并没有被去掉,并且由于 sort 没有将对象很好的排序,在对象部分,会出现一些去重失效

查找数组元素位置型

该类型即针对每个数组元素进行一次查找其在数组内的第一次出现的位置,若第一次出现的位置等于该元素此时的索引,即收集此元素

indexOf

indexOf 来查找元素在数组内第一次出现的位置,若位置等于当前元素的位置,则收集

function uniq(arr) {
    let res = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr.indexOf(arr[i]) === i) {
            res.push(arr[i]);
        }
    }
    return res;
}
// 运行结果
// [1, "1", "a", {}, {}, { a: 1 }, {}, { a: 1 }, [], [], [1], undefined, null];
// 与 lodash 结果相比 少了 NaN
复制代码

indexOf 采用与 === 相同的值相等判断规则,所以在数组内没有元素与 NaN 相等,包括它自己,所以 NaN 一个都不会被留下

findIndex

findIndex 方法来查找元素在数组内第一次出现的位置

function uniq(arr) {
    let res = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr.findIndex(item => item === arr[i]) === i) {
            res.push(arr[i]);
        }
    }
    return res;
}
// 运行结果
// [1, "1", "a", {}, {}, { a: 1 }, {}, { a: 1 }, [], [], [1], undefined, null];
// 与 lodash 结果相比 少了 NaN
复制代码

结果原理和 indexOf 相同,因为用了 === 的规则来判断元素是否相等,但此方法相当于双层 for 循环

查找元素是否存在型

该方法基本依托 includes 方法来判断对应元素是否在新数组内存在,若不存在则收集

function uniq(arr) {
    let res = [];
    for (let i = 0; i < arr.length; i++) {
        if (!res.includes(arr[i])) {
            res.push(arr[i]);
        }
    }
    return res;
}
// 运行结果
// [1, "1", "a", {}, {}, { a: 1 }, {}, { a: 1 }, [], [], [1], undefined, null, NaN];
// 与 lodash 结果相同
复制代码

includes 方法采用 SameValueZero 判断规则,所以可以判断出并去重 NaN

依托数据类型特性型

该方案依托于数据类型的不重复特性,以达到去重效果

Map

Map 类型的数据可以像 Object 一样,在设定元素键值对的时候可以保证键的唯一,并且将键的类型拓展到了基本所有元素,包括对象,在设定好一个唯一键的 Map 数据类型后,再用其自带的 Map.prototype.keys() 方法取到相应的键类数组,最后将类数组进行一次转化即可

function uniq(arr) {
    let map = new Map();
    for (let i = 0; i < arr.length; i++) {
        !map.has(arr[i]) && map.set(arr[i], true);
    }
    return [...map.keys()];
}
// 运行结果
// [1, "1", "a", {}, {}, { a: 1 }, {}, { a: 1 }, [], [], [1], undefined, null, NaN];
// 与 lodash 结果相同
复制代码

Set

与 Map 类似,运用数据类型的特性完成去重,这个方法也是最热门的方法

function uniq(arr) {
    return [...new Set(arr)];
}
// 运行结果
// [1, "1", "a", {}, {}, { a: 1 }, {}, { a: 1 }, [], [], [1], undefined, null, NaN];
// 与 lodash 结果相同
复制代码

性能测试

测试用例

这里简单(不严谨)的将刚才使用的测试例子拼接 100 万次

let a = {};
let b = { a: 1 };
let testArr = [1, 1, "1", "1", "a", "a", {}, {}, { a: 1 }, a, a, b, [], [], [1], undefined, undefined, null, null, NaN, NaN];
let arr = [];
for (let i = 0; i < 1000000; i++) {
    arr.push(...testArr);
}
uniq(arr);
复制代码

先说结果,在简单的测试用例大概 2000 万条数据下,indexOf 的方案速度相对最快

以上,就是我针对数组去重的总结,希望可以给大家一点 JS 数组去重的灵感,有不足的地方,欢迎指出一起讨论 😋

我之前还写过两个小工具,希望可以帮助到大家,一起学习一起进步。

关注下面的标签,发现更多相似文章
评论