乐趣区

关于javascript:JavaScript数组去重

jiezi

对一个长度为 n 的数组 arr 去重失去数组res，大略有三种办法：哈希 (hash)、排序和遍历。

遍历

遍历是暴力办法，也是最慢的办法。即对每个输出数组 arr 中的元素 arr[i]，都在后果数组res 中进行查找——若不存在，则将以后值 arr[i] 退出后果数组res；若已存在，则不再退出。

遍历实现数组去重

function deduplicateByBF(input) {let output = [];
    for (item of input) {if (output.indexOf(item) === -1) {output.push(item);
        }
    }
    return output;
}

let arr = [5, 77, 3, 43, 74, 2, 5, 3, 77, 2, 74, 43];
console.log(`Input:`, arr);

let res = deduplicateByBF(arr);
console.log(`Output:`, res);

//Input: [5, 77, 3, 43, 74, 2, 5, 3, 77, 2, 74, 43]
//Output: [5, 77, 3, 43, 74, 2]

工夫复杂度：T(n)=O(n²)
空间复杂度：S(n)=O(1)

排序

咱们先对输出数组 arr 排序，之后遍历一次输出数组arr。

因为曾经排序，反复值肯定相邻，所以在每一个地位 i 只须要判断以后值 arr[i] 是否等于前一个值 arr[i-1] 即可。
如果不等，则以后值为第一次呈现，记录后果；如果相等，则以后值曾经被记录，不再重复记录。

排序实现数组去重

function deduplicateBySorting(input) {let output = [];
    input.sort((a, b) => a - b);
    if (input.length > 0) {output.push(input[0]);
    }
    for (let i = 1; i < input.length; i++) {if (input[i] !== input[i - 1]) {output.push(input[i]);
        }
    }
    return output;
}

let arr = [5, 77, 3, 43, 74, 2, 5, 3, 77, 2, 74, 43];
console.log(`Input:`, arr);

let res = deduplicateBySorting(arr);
console.log(`Output:`, res);

//Input: [5, 77, 3, 43, 74, 2, 5, 3, 77, 2, 74, 43]
//Output: [2, 3, 5, 43, 74, 77]

工夫复杂度：T(n)=O(n·logn)
空间复杂度：S(n)=O(1)

应用排序的注意事项

以上例子应用的为全数字数组。如果有其余数据类型（如对象），依然能够应用，然而须要加以改进。

比方在比拟大小时不再应用(a, b) => a - b，而是先将二者序列化，再按字符串字典序比拟二者大小。但这种改良可能重大拖慢程序运行速度，该当防止。

所以，只有在确保输出数据为全数值数组的状况下才应用排序去重，否则请应用下文的 hash 去重。

Hash

Hash 简介

Hash（哈希）是用散列函数将指标对象转化为有代表性的特征值，这个特征值起到数组下标的作用，能够将指标对象映射到一个内存空间。

散列函数个别运算很快，所以通过 hash 来读写指标对象十分迅速，不须要如“遍历”等高耗时操作。通过设计适合的散列函数，hash 构造的索引均匀工夫复杂度为 O(1)。
相比于循环遍历数组构造，应用 hash 能够节省时间开销，但会减少空间开销（用于保留 hash table），属于“用空间换工夫”。

Set、map 都是常见的 hash 构造。Set 只记录某个元素是否被退出，map 则同时要记录元素对应的值（即保留键值对）。
JavaScript 中，对象的键值对实质上就是一种 map，也是通过 hash 实现的。

Hash 实现数组去重

function deduplicateByHashSet(input) {let output = [];
    let used = new Set();
    for (item of input) {if (!used.has(item)) {used.add(item);
            output.push(item);
        }
    }
    return output;
}

let arr = [5, 77, 3, 43, 74, 2, 5, 3, 77, 2, 74, 43];
console.log(`Input:`, arr);

let res = deduplicateByHashSet(arr);
console.log(`Output:`, res);

//Input: [5, 77, 3, 43, 74, 2, 5, 3, 77, 2, 74, 43]
//Output: [5, 77, 3, 43, 74, 2]

工夫复杂度：T(n)=O(n)
空间复杂度：S(n)=O(n)

后记

很多人对数组去重这个简略问题洋洋洒洒列举出了七八种解决办法，但这些办法不过是上述暴力遍历和 hash 的批改：例如把 Set 改为 Map 或者 Object 的属性，把调用 indexOf 办法改为用手写 for 循环实现。

这些批改在我看来没有意义，很多文章甚至没有想到排序的办法——这些乱象催生了这篇文章。

心愿对你有所帮忙。

退出移动版