数组去重

[huitoutunao]

数组去重

数组去重，不仅会在项目开发中运用到，还会被选作为面试题。因此，我们来捋一捋数组去重的几种方案。

嵌套循环

这种方式兼容性好。

var array = [1, 'a', 1, 'a']

function unique (arr) {
    var res = []

    for (var i = 0, iLen = arr.length; i < iLen; i++) {
        for (var k = 0, kLen = res.length; k < kLen; k++) {
            if (arr[i] === res[k]) {
                break
            }
        }

        // 判断 res 数组有无一一与 arr 数组对比
        // 如果为 true，那么这个 arr[i] 就是唯一值，否则为重复值
        if (k === kLen) {
            res.push(arr[i])
        }
    }

    return res
}
console.log(unique(array)) // [1, "a"]

indexOf

indexOf() 方法返回在数组中可以找到一个给定元素的第一个索引，如果不存在，则返回-1

var array = [1, 'a', 1, 'a']

function unique (arr) {
    var res = []
    for (var i = 0, iLen = arr.length; i < iLen; i++) {
        var cur = arr[i]
        if (res.indexOf(cur) === -1) {
            res.push(cur)
        }
    }
    return res
}

console.log(unique(array)) // [1, "a"]

sort

sort() 方法用原地算法对数组的元素进行排序，并返回数组。默认排序顺序是在将元素转换为字符串，然后比较它们的 UTF-16 代码单元值序列时构建的

使用 sort() 方法进行数组排序后去重。判断相邻元素是否相同，相同的就不添加进 res 结果数组。

var arr = [1, 2, 1, 1, '1']

function unique (arr) {
    var res = []
    var sortArray = arr.concat().sort() // arr.concat() 目的是复制一份原数组，使后面操作不影响原数组
    var memory

    for (var i = 0, len = arr.length; i < len; i++) {
        if (!i || memory !== sortArray[i]) {
            res.push(sortArray[i])
        }
        memory = sortArray[i]
    }

    return res
}

console.log(unique(arr)) // [1, "1", 2]

filter

filter() 方法创建一个新数组, 其包含通过所提供函数实现的测试的所有元素。

结合 indexOf 的方法使用：

var arr = [1, 2, 1, 1, '1']

function unique (arr) {
    return arr.filter(function (item, index, array) {
        return array.indexOf(item) === index
    })
}
console.log(unique(arr)) // [1, "1", 2]

结合排序去重方法使用：

var arr = [1, 2, 1, 1, '1']

function unique (arr) {
    return arr.concat().sort().filter(function (item, index, array) {
        return !index || item !== array[index -1]
    })
}
console.log(unique(arr)) // [1, "1", 2]

Object 键值对 + filter + hasOwnProperty

hasOwnProperty() 方法会返回一个布尔值，指示对象自身属性中是否具有指定的属性（也就是，是否有指定的键）。

思路：创建一个空对象 obj，将要过滤数组 arr 的值存成 obj 的键名，判断键名不能重复来达到过滤的目的。

问题：对象的键名都是字符串类型，例如：1 和 '1' 在保存成键名时是一样的。

解决：使用数组每项值类型名+值来作为键名。

var arr = [1, 2, 1, 1, '1']

function unique (arr) {
    var obj = {}
    return arr.filter(function (item, index, array) {
        return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true)
    })
}
console.log(unique(arr)) // [1, "1", 2]

如果遇到数组中包含多个对象，使用刚刚介绍的方法会有点问题，因为执行 typeof item + item 这句代码的结果是 object[object Object]，可以使用 JSON.stringify 将对象序列化。

var arr = [{v: 1}, {v: 1}, {v: 3}]

function unique (arr) {
    var obj = {}
    return arr.filter(function (item, index, array) {
        return obj.hasOwnProperty(typeof item + JSON.stringify(item)) ? false : (obj[typeof item + JSON.stringify(item)] = true)
    })
}
console.log(unique(arr)) // [{v: 1},{v: 3}]

时间复杂度 O(n)

和上面的思路一样，只是不使用数组的方法。具体见下面实现代码：

function unique (arr) {
    var nArr = []
    var obj = {}
    var index = 0

    for (var i = 0, len = arr.length; i < len; i++) {
        var item = arr[i]
        if (!obj.hasOwnProperty(typeof item + JSON.stringify(item))) {
            nArr[index++] = arr[i]
            obj[typeof item + JSON.stringify(item)] = true
        }
    }

    return nArr
}

var arr = [1, 1, '3', 3, 3, 2, '2', 2,  {v: 1}, {v: 2}, {v: '1'}, {v: 1}]
console.log(unique(arr))
// => [1,"3",3,2,"2",{v: 1},{v: 2},{v: "1"}]

includes

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

var arr = [1, 2, 1, 1, '1']

function unique (arr) {
    var res = []
    for (var i = 0, len = arr.length; i < len; i++) {
        if (!res.includes(arr[i])) {
            res.push(arr[i])
        }
    }
    return res
}
console.log(unique(arr)) // [1, "1", 2]

Map

Map 对象保存键值对，并且能够记住键的原始插入顺序。任何值(对象或者原始值) 都可以作为一个键或一个值。

var arr = [1, 2, 1, 1, '1']

function unique (arr) {
    var memory = new Map()
    return arr.filter((item) => !memory.has(item) && memory.set(item, true))
}
console.log(unique(arr)) // [1, "1", 2]

Set

Set 对象允许你存储任何类型的唯一值，无论是原始值或者是对象引用。

Set 的介绍可以看出它就是为数组去重而生啊。

var arr = [1, 2, 1, 1, '1']
var unique = (arr) => [...new Set(arr)]
console.log(unique(arr)) // [1, "1", 2]

特殊类型

上面去重的数组元素类型都比较常规，如果遇到特殊类型元素，例如：null、NaN、undefined 和 {} 等，那么去重方法返回的结果会有什么不同呢？请看这篇文章——特殊类型比较。

结语

通过上面总结可以得知，去重方式有多种，且它们对待特殊类型的去重结果也会不同，但是我们可以根据业务场景选择适合的去重方式。