如何精彩的回答出数组去重方法

/ 4评 / 0
内容纲要

老生常谈,数组去重一直是面试官喜欢问的问题,它并不是一道特别难的问题,但是能看出一个人的广度和深度,以及考虑事情的全面性。

常用的去重方法

双层 for 循环

function distinct(arr) {
    for (let i=0, len=arr.length; i<len; i++) {
        for (let j=i+1; j<len; j++) {
            if (arr[i] == arr[j]) {
                arr.splice(j, 1);
                // splice 会改变数组长度,所以要将数组长度 len 和下标 j 减一
                len--;
                j--;
            }
        }
    }
    return arr;
}

双重 for 循环是比较笨拙的方法,它实现的原理很简单:先定义一个包含原始数组第一个元素的数组,然后遍历原始数组,将原始数组中的每个元素与新数组中的每个元素进行比对,如果不重复则添加到新数组中,最后返回新数组;因为它的时间复杂度是O(n^2),如果数组长度很大,效率会很低。

Array.filter() 加 indexOf

function distinct(arr) {
    return arr.filter((item, index)=> {
        return arr.indexOf(item) === index
    })
}

利用indexOf检测元素在数组中第一次出现的位置是否和元素现在的位置相等,如果不等则说明该元素是重复元素

Array.sort() 加一行遍历冒泡(相邻元素去重)

function distinct(array) {
    var res = [];
    var sortedArray = array.concat().sort();
    var seen;
    for (var i = 0, len = sortedArray.length; i < len; i++) {
        // 如果是第一个元素或者相邻的元素不相同
        if (!i || seen !== sortedArray[i]) {
            res.push(sortedArray[i])
        }
        seen = sortedArray[i];
    }
    return res;
}

调用了数组的排序方法 sort(),V8引擎 的 sort() 方法在数组长度小于等于10的情况下,会使用插入排序,大于10的情况下会使用快速排序。根据排序后的结果进行遍历及相邻元素比对(其实就是一行冒泡排序比较),如果相等则跳过该元素,直到遍历结束。

ES6中的Set去重

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

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

Object 键值对

function distinct(array) {
    var obj = {};
    return array.filter(function(item, index, array){
        return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true)
    })
}

这种方法是利用一个空的 Object 对象,我们把数组的值存成 Object 的 key 值,比如 Object[value1] = true,在判断另一个值的时候,如果 Object[value2]存在的话,就说明该值是重复的,但是最后请注意这里obj[typeof item + item] = true没有直接使用obj[item],是因为 123 和 '123' 是不同的,直接使用前面的方法会判断为同一个值,因为对象的键值只能是字符串,所以我们可以使用 typeof item + item 拼成字符串作为 key 值来避免这个问题。

性能考虑

let arr1 = Array.from(new Array(100000), (x, index)=>{
    return index
})

let arr2 = Array.from(new Array(50000), (x, index)=>{
    return index+index
})

let start = new Date().getTime()
console.log('开始数组去重')

let arr = a.concat(b);

function distinct(arr) {
    // 数组去重
}

console.log('去重后的长度', distinct(arr).length)

let end = new Date().getTime()
console.log('耗时', end - start)

双重 for 循环 > Array.filter()加 indexOf > Array.sort() 加一行遍历冒泡 > ES6中的Set去重 > Object 键值对去重复

4条回应:“如何精彩的回答出数组去重方法”

  1. ExoRank说道:

    Awesome post! Keep up the great work! 🙂

  2. AffiliateLabz说道:

    Great content! Super high-quality! Keep it up! 🙂

  3. cbd说道:

    Wow, that’s what I was seeking for, what a information! present here at this blog, thanks admin of
    this web page.

  4. cbd oil for sale说道:

    My brother suggested I might like this web site.

    He used to be entirely right. This submit actually made my day.
    You cann’t believe just how much time I had spent for this info!
    Thank you!

发表评论

电子邮件地址不会被公开。