数组去重

发表于   |   分类于

常规法（最直观的思路）

1
2
3
4
5
6
7
8
9
10
11
12
13
function unique(arr){
    var n = []; //创建一个新数组
    for(var i = 0; i < arr.length; i++) {
    //如果新数组中已经包含了当前的第i个元素，那么跳过
        if (n.indexOf(arr[i]) == -1) {
    //否则把当前项push到新数组中
            n.push(arr[i]);
        }
    }
    return n;
}
var array = [4,2,4,6,1,2,4,7,8];
console.log(unique(array)); //输出[4,2,6,1,7,8]

这种方法用到了indexOf方法。其目的是寻找参数在数组中第一次出现的位置。很显然，js引擎在实现这个方法的时候会遍历数组直到找到目标为止。所以此函数会浪费掉很多时间，效率并不高。

第二种：hash()表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function unique(arr){
    var n = [];
    var hash = {};
    for(var i = 0; i < arr.length; i++){
        if (!hash[arr[i]])//如果hash表中不存在
        {
            hash[arr[i]] = 1;
            n.push(arr[i])
        }
    }
    return n;    
}
var array = [4,2,4,6,1,2,4,7,8];
console.log(unique(array));//输出[4,2,6,1,7,8]

当for循环遍历数组时，每次取出一个元素与hash表中的对象进行对比，如果这个元素不重复，则把它存放到结果数组中，同时把这个元素的内容作为对象的一个属性，并赋值为1，存入到hash表中。

第三种：先排序在比较相邻元素

1
2
3
4
5
6
7
8
9
10
11
12
function unique(arr){
    arr.sort();
    var n = [arr[0]];
    for(var i = 1; i < arr.length; i++){
        if(arr[i] !== n[n.length-1]){
            n.push(arr[i]);
        }
    }
    return n;
}
var array = [4,2,4,6,1,2,4,7,8];
console.log(unique(array)); //输出[1,2,4,6,7,8]

排序的时候用的JS原生的sort方法，JS引擎内部用的快速排序。最终测试的结果是此方法运行时间比上面两种都快了不少。

特殊情况：

当数组中既有数字又有字符串的时候，如： var arr = [4,2,4,6,1,”2”,4,7,8] ,此时希望2和”2″都保留，那么上述的方法无法达到要求。

第四种：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function unique(arr){
    var n = [];
    var hash = {};
    for(var i = 0; i < arr.length; i++){
        if (!hash[typeof(arr[i])+arr[i]])
        {
            hash[typeof(arr[i])+arr[i]] = 1;
            n.push(arr[i])
        }
    }
    return n;    
}
var array = [4,2,4,6,1,"2",4,7,8];
console.log(unique(array));//输出[4,2,6,1,"2",7,8]

在 JavaScript 里，对象的键值只能是字符串，因此需要 typeof(arr[i])+arr[i] 来区分数值 2 和字符串 “2” 的情况。