2019-08-15 | JavaScript, 算法, 数组去重

算法之数组的去重

1. 数组的去重（处理基本类型）

方法一：

// 数组去重
// 它的时间复杂度为O(n^2)，因为它有两个两个循环，
// 第一个为"for of"循环，第二个为indexOf循环，因为indexOf需要遍历整个数组去查。
        let arr = ["1",2,3,"a",3,5,"a",{a:1}];
        function unique(arr){
            let result = [];
            for(let key of arr){
                if(result.indexOf(key) === -1){
                    result.push(key);
                }
            }
            return result;
        }
        console.log(unique(arr));  // ["1", 2, 3, "a", 5, {a: 1}]

方法二：

// 数组去重
// 如果你想缩小时间复杂度，可以先使用sort方法给它进行一个排序，
// 然后再使用for循环来看它后面是否是和它相同的内容。
// 时间复杂度为O(nlogN)
        let arr = ["1",2,3,"a",3,5,"a",{a:1}];
        function unique2(arr){  // 整个算法的时间复杂度为O(nlogN)，因为我们去它们之间最大的那一个时间复杂度
            let result = [];
            arr.sort();   // sort最快的时间复杂度为O(nlogN)
            console.log(arr); // ["1", 2, 3, 3, 5, {a: 1}, "a", "a"]
            for(let i = 0 ; i < arr.length ; i++){  // for循环时间复杂度为O(n)
                if(arr[i] !== arr[i+1]){
                    result.push(arr[i]);
                }
            }
            return result;
        }
// 需要注意：是没有按照原始数据的顺序来排序
        console.log(unique2(arr));  // ["1", 2, 3, 5, {a: 1}, "a"]

方法三：

 // 数组去重
// 使用Object.keys方法，但是不好之处就是最后打印出来的结果都变成了字符串
// 时间复杂度为:O(n)
        let arr = ["1",2,3,"a",3,5,"a",{a:1}];
        function unique3(arr){
            let obj = {};
            for(let key of arr){
                obj[key] = true;  // 如果它是相同的，那么这个值对于这个对象就没有做任何的修改
            }
            return Object.keys(obj);
        }
        console.log(unique3(arr));  // ["1", "2", "3", "5", "a", "[object Object]"]

方法四：

// 数组去重
// 最简单的一种方法，使用es6中的Set集合类和Array.from方法
// 时间复杂度为:O(n)
        let arr = ["1",2,3,"a",3,5,"a",{a:1}];
        function unique4(arr){
            let set = new Set(arr);
            return Array.from(set);
        }
        console.log(unique4(arr));  // ["1", 2, 3, "a", 5, {a: 1}]

方法五：

// 数组去重
       // 自己手动封装的一个去重方法
       let arr = ["1",2,3,"a",3,5,"a",{a:1}];
       Array.prototype.unique5 = function(){   // 给数组Array添加一个原型方法
           let ret = [];
           for(let i = 0 ; i < this.length ; i++){
               for(let j = i + 1 ; j < this.length ; ){
                   if(this[i] === this[j]){
                       ret.push(this.splice(j,1)[0]);
                   }else{
                       j++;
                   }
               }
           }
           return ret;
       };
       arr.unique5();
       console.log(arr); // ["1", 2, 3, "a", 5, {a: 1}]

注意：上面五种方法处理引用类型是有问题的。

2. 数组的去重（处理引用类型）

方法一：

// 数组去重（处理引用类型）
        // 利用对象的键名不能重复的特点
        function unique(arr){
            let obj = {};
            arr.forEach(function(item){
                obj[JSON.stringify(item)] = item;  // 键名不会重复
            });
            // Object.keys()返回对象的所有键值组成的数组，map方法是一个遍历方法，
            // 返回遍历结果组成的数组，将unique对象的键名还原成对象数组。
            arr = Object.keys(obj).map(function(item){
                return JSON.parse(item);
            });
            return arr;
        }
        let arr = ["1",2,3,"a",{a:1},3,5,"a",{a:1}];
        console.log(unique(arr));  // [2, 3, 5, "1", "a", {a: 1}]
        // 缺点：比如{a: 1,b: 2}和{b: 2,a: 1}(数组也是如此)通过JSON.stringify转化为字符串值不同，
        // 但是显然它是一个重复的对象，此时不能将它去重掉，如下所示：
        let arr1 = ["1",2,3,"a",{a:1,b:2},3,5,"a",{b:2,a:1}];
        console.log(unique(arr1));  // [2, 3, 5, "1", "a", {a: 1,b: 2}, {b: 2,a: 1}]

它的缺点：缺点：比如{a: 1,b: 2}和{b: 2,a: 1}(数组也是如此)通过JSON.stringify转化为字符串值不同，但是显然它是一个重复的对象，此时不能将它去重掉。

方法二：
使用lodash工具库中的_.uniqWith()来实现。