参见英文答案 >
Easiest way to find duplicate values in a JavaScript array47
众所周知,没有内置的功能可以从javascript中的数组中删除重复的内容.我注意到,这也是缺乏jQuery(它只有DOM选择的唯一功能),我发现最常见的代码片段检查整个数组和每个元素的一个子集(不是非常有效率,我认为),像：
众所周知,没有内置的功能可以从javascript中的数组中删除重复的内容.我注意到,这也是缺乏jQuery(它只有DOM选择的唯一功能),我发现最常见的代码片段检查整个数组和每个元素的一个子集(不是非常有效率,我认为),像：
for (var i = 0; i < arr.length; i++)
for (var j = i + 1; j < arr.length; j++)
if (arr[i] === arr[j])
//whatever
所以我自己做：
function unique (arr) {
var hash = {},result = [];
for (var i = 0; i < arr.length; i++)
if (!(arr[i] in hash)) { //it works with objects! in FF,at least
hash[arr[i]] = true;
result.push(arr[i]);
}
return result;
}
我想知道是否有任何其他算法被接受为最好的这种情况(或者如果你看到任何明显的缺陷可以修复),或者你在JavaScript中需要这样做(我知道jQuery不是只有框架和其他一些可能已经覆盖了).
解决方法
使用对象文字就是我会做的.很多人很想念这项技术,而是选择典型的阵列散步作为您显示的原始代码.唯一的优化是避免每次查找arr.length.除此之外,O(n)与您获得的唯一性一样好,并且比原来的O(n ^ 2)示例好得多.
function unique(arr) {
var hash = {},result = [];
for ( var i = 0,l = arr.length; i < l; ++i ) {
if ( !hash.hasOwnProperty(arr[i]) ) { //it works with objects! in FF,at least
hash[ arr[i] ] = true;
result.push(arr[i]);
}
}
return result;
}
// * Edited to use hasOwnProperty per comments
时间复杂性总结
f() | unsorted | sorted | objects | scalar | library ____________________________________________________________ unique | O(n) | O(n) | no | yes | n/a original | O(n^2) | O(n^2) | yes | yes | n/a uniq | O(n^2) | O(n) | yes | yes | Prototype _.uniq | O(n^2) | O(n) | yes | yes | Underscore
与大多数算法一样,还有权衡.如果您只排序标量值,则您对原始算法的修改提供最佳解决方案.但是,如果您需要排序非标量值,则使用或模拟所讨论的任一库的uniq方法将是您的最佳选择.