#健康快乐工作#每一天都是新的一天

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方法


四、排序后去重

思路:使用快排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。

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

注意: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排序时候存在一个隐式转换。


六、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]


七、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]


八、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,为了解决对象中的键只能是字符串的问题,其实其他基本数据类型是可以作为键的。


九、特殊数据类型比较

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之内的方式?


文章转载:原创
感谢你的阅读,本文由 sau交流学习社区 版权所有。
如若转载,请注明出处:sau交流学习社区-power by saucxs(程新松)(/page/723.html)
交流咨询
    官方QQ群
    群号663940201,欢迎加入!
    sau交流学习社区交流群

图文推荐

saucxs聊天机器人
saucxs
hi ,欢迎来到sau交流学习社区,欢迎与我聊天,问我问题哦!