数组去重是开发中常见的需求，有很多种实现方法

纯数字数组的去重

双重循环

将外层循环的元素与内层循环的值相比较，相同时删除，时间复杂度为$O(n^3)$（splice本身需要循环一次），空间复杂度为$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
function unique_double_loop(arr) {
    let len = arr.length, result = []
    for (let i = 0; i < len; i++) {
        for (let j = 1 + 1; j < len; j++) {
            if (arr[i] === arr[j]) {
                arr.splice(j, 1)
                len--
                j--
            }
        }
    }
    return arr
}

filter + indexOf

核心思想是如果该元素在数组中第一次出现时的序号等于当前的序号，则未重复，时间复杂度为$O(n^2)$，空间复杂度为$O(n)$

1
2
3
4
5
function unique_filter(arr) {
    return arr.filter((item, index, arr) => {
        return arr.indexOf(item) === index
    })
}

排序

将数组排序后再遍历一遍去重，时间复杂度为$O(nlogn)$，空间复杂度为$O(n)$

1
2
3
4
5
6
7
8
9
10
function unique_sort(arr) {
    arr = arr.sort()
    let len = arr.length, result = [arr[0]]
    for (let i = 1; i < len; i++) {
        if (arr[i] !== arr[i - 1]) {
            result.push(arr[i])
        }
    }
    return result
}

new Set

ES6 提供了新的数据结构 Set，Set 结构的一个特性就是成员值都是唯一的，没有重复的值，时间复杂度为$O(n)$，空间复杂度为$O(n)$

1
2
3
function unique_new_set(arr) {
    return Array.from(new Set(arr))
}

哈希表去重

利用一个空的 Object 对象，把数组的值存成 Object 的 key 值，比如Object[value1] = true，在判断另一个值的时候，如果Object[value2]存在的话，就说明该值是重复的，时间负杂度为$O(n)$，空间复杂度为$O(n)$

1
2
3
4
5
6
7
8
9
10
11
function unique_object(arr) {
    let obj = {}, result = []
    let len = arr.length
    for (let i = 0; i < len; i++) {
        if (!obj[arr[i]]) {
            result.push(arr[i])
            obj[arr[i]] = true
        }
    }
    return result
}

性能比较

取一个长度为 100000 的数组，数组内为 0~3000 的随机整数进行去重，每个方法分别指向 20 次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 测试数组
const testArr = Array.from({ length: 100000 }, () => Math.random() * 3000 | 0)

// 测试方法
function runtime(func, times) {
    let time = []

    for (let i = 0; i < times; i++) {
        let _testArr = testArr.slice()
        let start = process.hrtime.bigint()
        func.call(this, _testArr)
        let end = process.hrtime.bigint()
        time.push(Number(end - start) / 1000000)
    }

    return time
}

结果如下

数组去重算法性能比较

可以看到，结果基本符合上文中的时间复杂度的顺序，双重循环性能最差，Set 和 哈希表方法最优，其中哈希表性能优于 Set 方法

多种数据类型去重

在 JavaScript 中对象是引用类型，无法用 === 直接判断是否相等；而 NaN 等数据类型同样不能判断

以哈希表去重为基础作如下修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function unique(arr) {
    let obj = {}, result = []
    let len = arr.length
    for (let i = 0; i < len; i++) {
        let _key
        switch (typeof arr[i]) {
            case 'object':
                _key = JSON.stringify(arr[i])
                break
            case 'function':
                _key = arr[i].toString()
                break
            case 'undefined':
                _key = 'undefined'
                break
            case 'string':
                _key = '_' + arr[i]
                break
            default:
                _key = arr[i]
                break;
        }
        if (Number.isNaN(arr[i])) _key = '_' + 'NaN'
        if (!obj[_key]) {
            result.push(arr[i])
            obj[_key] = true
        }
    }
    return result
}

运行

1
2
unique([{}, {}, { a: 1 }, { a: 1 }, () => 1, () => 1, 1, 1, '2', '2', 2, NaN, NaN])
// [ {}, { a: 1 }, [Function], 1, '2', 2, NaN ]