JavaScript系列八种数组去重方法的总结

一、前言

数组去重是一个老生常谈的问题，但是有时候会弹出点其他东西。

二、双重循环

这个方法是最常见的，最原始的方法。

// 方法一：双重循环
var array = [1,1,'1','2','1',1,2]

function unique(arr){
    // res 存结果
    var res = [];
    for(var i = 0, length = arr.length; i < length; i++){for(var j = 0, length2 = res.length; j < length2; j++){if(arr[i] === res[j]){break;}
        }
        if(j == length2){res.push(arr[i])
        }
    }
    return res;
}

unique(array);  //[1, "1", "2", 2]

思路：双层循环方法，使用的是循环嵌套，外层是 arr，里层是 res，如果 arr[i]的值等于 res[j]的值，则跳出当前循环，如果都不等于，说明元素唯一，这时候 j 的值等于 res 的长度，根据这个判断，将值添加 res 中。

优点：兼容性好

缺点：时间复杂度 o(n2)

三、indexOf 方法

思路：使用 indexOf 简化内层循环。

// 方法二：indexOf 简化内层循环
var array = [1,1,'1','2','1',1,2]

function unique(arr){
    // res 存结果
    var res = [];
    for(var i = 0, length = arr.length; i < length; i++){var current = arr[i];
       if(res.indexOf(current) === -1){res.push(current);
       }
    }
    return res;
}

unique(array);   //[1, "1", "2", 2]

优点：时间复杂度降低

缺点：有的浏览器不支持 indexOf 方法，时间复杂度 o(n2)

四、排序后去重

思路：使用快排 sort 将数组排序，这样相同的值会被排在一起，只需要判断当前元素与上一个元素是否相同，相同说明重复，不同就添加进 res 中。

// 方法三：排序后去重
var array = [1,1,'1','2','1',1,2]

function unique(arr){
    // res 存结果
    var res = [];
    var sortedArray = arr.concat().sort();
    console.log(sortedArray, '-=-=-=-=-=-=')
    var current;
    for(var i = 0, length = sortedArray.length; i < length; i++){
        // 如果是第一个元素 或者是相邻元素不相同
       if(!i || current !== sortedArray[i]){res.push(sortedArray[i]);
       }
       current = sortedArray[i];
    }
    return res;
}

unique(array);   //[1, "1", 1, "2", 2]

优点：已经排好序的数组去重，这种方法效率高于使用 indexOf，时间复杂度 o(n)

缺点：已经修改数组的顺序，同时存在去重不彻底

注意：sort 函数默认排序是 Unicode，srot 方法默认可是能给字母实现排序。突然发现了 sort 在排序的时候存在一个隐式转换，会把要排序的对象转换成字符串，sort 排序的时候 1 和 ’1’ 是相同的，然后根据 unicode 比较大小，所以出现了 [1, “1”, 1, “2”, 2] 这种情况。

注意：数组进行了 array.concat()操作之后，其实是复制出来一份原有的数组，复制出来的新数组不会影响到原有数组。

五、使用 ES5 的 filter

思路：使用 filter 简化外层循环

1、使用 indexOf 简化内层循环

// 方法四：filter + indexOf
var array = [1,1,'1','2','1',1,2]

function unique(arr){
    // res 存结果
    var res = arr.filter(function(item, index, arr){return arr.indexOf(item) === index;
    })
    return res;
}

unique(array);   //[1, "1", "2", 2]

2、排序去重的方法

// 方法四：filter + sort
var array = [1,1,'1','2','1',1,2]

function unique(arr){
    // res 存结果
    var res = arr.concat().sort().filter(function(item, index, arr){return !index ||  item !==arr[index -1]
    })
    return res;
}

unique(array);   //[1, "1", 1, "2", 2]

上面已经讲到了 sort 排序时候存在一个隐式转换。

优点：很简洁，思维也比较巧妙，直观易懂，使用 filter 简化外层循环

缺点：不支持 IE9 以下的浏览器，时间复杂度 o(n*2)

六、Object 键值对的问题

思路：利用一个空的 Object 对象，把数组的值存成 Object 的 key，比如就是 Object[value] = true; 循环判断的时候，如果 Object[value]存在，说明这个值重复了。

// 方法五：Object 键值对
var array = [1,1,'1','2','1',1,2]

function unique(arr){
    // obj 存对象
    var obj= {};
    var res = arr.filter(function(item, index, arr){if(obj.hasOwnProperty(item)) return false;
        else {return obj[item] = true;
        }
    })
    return res;
}

unique(array);   //[1, "2"]

然后我们发现 1 和 ’1’ 是不同的，但是这种方法会判断为是同一个值，因为键值对中只能是字符串，会进行一个隐式转换。和 sort 排序时候的转换是一样的，可以通过 typeof item+ item，拼成字符串作为 key 的值避免这个问题

// 优化
function unique(arr){
    // obj 存对象
    var obj= {};
    var res = arr.filter(function(item, index, arr){if(obj.hasOwnProperty(typeof item + item)) return false;
        else {return obj[typeof item + item] = true;
        }
    })
    return res;
}

unique(array);   //[1, "1", "2", 2]

优点：hasOwnProperty 是对象的属性存在性检查方法。对象的属性可以基于 hash 表实现，因此对属性的方法的时间复杂度达到 O(1)；filter 是数组迭代的方法，内部是一个 for 循环，复杂度 O(n)。总的时间复杂度 O(n)。

缺点：不兼容 IE9 以下浏览器

七、reduce 高阶函数

includes() 方法用来判断一个数组是否包含一个指定的值，根据情况，如果包含则返回 true，否则返回 false。

// 方法六：reduce 高阶函数
var array = [1,1,'1','2','1',1,2]
function unique(arr){let newArr = arr.reduce((pre,cur)=>{if(!pre.includes(cur)){return pre.concat(cur)
        }else{return pre}
    },[]);
    return newArr;
}
console.log(unique(array));// [1, "1", "2", 2]

优点：高阶函数的高级用法。

缺点：兼容性问题，对象数组不能使用 includes 方法来检测。includes 区分大小写

八、ES6 的 Set 数据结构

只能说 ES6 标准越来越好，可以使用 Set 数据结构，ES6 中提供了 set 数据结构，类似于数组，成员值都是唯一的，没有重复的。

// 方法七：ES6 的 set
var array = [1,1,'1','2','1',1,2]

function unique(arr){return Array.from(new Set(arr));
}

unique(array);   //[1, "1", "2", 2]

还可以用扩展运算符 …

// 优化
var array = [1,1,'1','2','1',1,2]

function unique(arr){return  [...new Set(arr)];
}

unique(array);   //[1, "1", "2", 2]

再写简单点

// 再优化
var array = [1,1,'1','2','1',1,2]

const unique = arr => [...new Set(arr)];

unique(array);   //[1, "1", "2", 2]

优点：ES6 语法简单高效。

缺点：兼容性问题，加上使用 babel 编译不是问题。

九、ES6 的 Map 数据结构

// 方法八：ES6 的 Map + filter
var array = [1,1,'1','2','1',1,2];

function unique(arr){var current = new Map();
    var res = arr.filter(function(item, index, arr){if(current.has(item)){return false;}else{return current.set(item, 1);
        }
    })
    return res;
}

unique(array);   //[1, "1", "2", 2]

思路：使用 map 的方法 set 和 has，用 has 方法来判断是否存在这个 key，如果没有值将 map 中存一个 key-value。

注意：最新的 ES6 规范引入了新的数据类型 Map，为了解决对象中的键只能是字符串的问题，其实其他基本数据类型是可以作为键的。

优点：ES6 语法简单高效。

缺点：兼容性问题，加上使用 babel 编译不是问题。

十、特殊数据类型比较

var str1 = '1';
var str2 = new String('1');

console.log(str1 == str2); // true
console.log(str1 === str2); // false

console.log(null == null); // true
console.log(null === null); // true

console.log(undefined == undefined); // true
console.log(undefined === undefined); // true

console.log(NaN == NaN); // false
console.log(NaN === NaN); // false

console.log(/a/ == /a/); // false
console.log(/a/ === /a/); // false

console.log({} == {}); // false
console.log({} === {}); // false

看个栗子 1

var arr = [1, 2, NaN];
arr.indexOf(NaN); // -1

原因：indexOf 底层还是使用 === 来进行判断的，因为 NAN === NAN 结果是 false，使用 indexOf 还是查不到 NAN 这个元素。

再看个栗子 2

function unique(array) {return Array.from(new Set(array));
}
console.log(unique([NaN, NaN])) // [NaN]

Set 中，NAN === NAN 是 false，但是这两个元素是重复的

十一、后话

在对数组去重的性能进行优化，然后想了半天也只写出来了 Object 键值对的性能，找不到其他既能判断引用类型，性能又稳定在 n^2 之内的方式？

自己回答一下：

目前时间复杂度到 O(n)的方法：

（1）Object 键值对，实质是 hasOwnProperty 的 hash 表。

（2）ES6 的 set，map 的数据结构

（3）reduce 高阶函数

【注：我是 saucxs，也叫 songEagle，松宝写代码，文章首发于 sau 交流学习社区（https://www.mwcxs.top），关注我们每天阅读更多精彩内容】