JavaScript 知识梳理 [七] 解锁多种JavaScript数组去重姿势

蔚落 2022-11-26 08:49 135阅读 0赞

> 今天又是工作不饱和的一天，react 学习了一段时间也该换换脑子，那么JavaScript 知识梳理再开始吧！看到了一篇，自己也敲了一遍试了试，那么搬运过来，以做记录。

转至：[https://juejin.im/post/6844903608467587085\#heading-6][https_juejin.im_post_6844903608467587085_heading-6]

整体代码架构，生成模拟数组

// 生成模拟数据
    const arr = []
    for (let i = 0; i < 100000; i++) {
         arr.push(Math.floor(100000 * Math.random()))
      }
    
    // ...实现算法
    
    console.time('test');
    arr.unique();
    console.timeEnd('test');

去重算法

### 双重for循环 ###

// 方法一
            Array.prototype.unique = function () {
                const newArray = []
                let isRepeat;
                for (let i = 0; i < this.length; i++) {
                    isRepeat = false
                    for (let j = 0; j < newArray.length; j++) {
                        if (this[i] === newArray[j]) {
                            isRepeat = true
                            break;
                        }
                    }
                    if (!isRepeat) {
                        newArray.push(this[i])
                    }
                }
                return newArray
            }
    
    
            // 方法二 
            Array.prototype.unique = function () {
                const newArray = [];
                let isRepeat;
                for (let i = 0; i < this.length; i++) {
                    isRepeat = false;
                    for (let j = i + 1; j < this.length; j++) {
                        if (this[i] === this[j]) {
                            isRepeat = true;
                            break;
                        }
                    }
                    if (!isRepeat) {
                        newArray.push(this[i]);
                    }
                }
                return newArray;
            }
    
    
            // 方法三
            Array.prototype.unique = function () {
                const newArray = [];
    
                for (let i = 0; i < this.length; i++) {
                    for (let j = i + 1; j < this.length; j++) {
                        if (this[i] === this[j]) {
                            j = ++i;
                        }
                    }
                    newArray.push(this[i]);
                }
                return newArray;
            }

### Array.prototype.indexOf() ###

*基本思路： 如果索引不是第一个索引， 说明是重复值。*

// 实现一：
    
            // 利用Array.prototype.filter() 过滤功能
            // Array.prototype.indexOf() 返回的是第一个索引值
            // 只将数组中元素第一次出现的返回
            // 之后出现的将被过滤掉   test: 6530.6240234375ms
    
            Array.prototype.unique = function () {
                return this.filter((item, index) => {
                    return this.indexOf(item) === index;
                })
            }
    
            //test: 4513.012939453125ms
            Array.prototype.unique = function () {
                const newArray = []
                this.forEach(item => {
                    if (newArray.indexOf(item) === -1) {
                        newArray.push(item)
                    }
                })
                return newArray
            }

### Array.prototype.sort() ###

*基本思路：先对原数组进行排序，然后再进行元素比较。*

// 实现一：test: 68.82080078125ms
            Array.prototype.unique = function () {
                const newArray = []
                this.sort()
                for (let i = 0; i < this.length; i++) {
                    if (this[i] !== this[i + 1]) {
                        newArray.push(this.i)
                    }
                }
                return newArray
            }
    
            // 实现二  test2.html:165 test: 66.434326171875ms
            Array.prototype.unique = function () {
                const newArray = [];
                this.sort();
                for (let i = 0; i < this.length; i++) {
                    if (this[i] !== newArray[newArray.length - 1]) {
                        newArray.push(this[i]);
                    }
                }
                return newArray;
            }

### Array.prototype.includes() ###

// Array.prototype.includes() 
            // test: 4593.318115234375ms
            Array.prototype.unique = function () {
                const newArray = []
                this.forEach(item => {
                    if (!newArray.includes(item)) {
                        newArray.push(item)
                    }
                })
                return newArray
            }

### Array.prototype.reduce() ###

//test: 68.841064453125ms
            Array.prototype.unique = function () {
                return this.sort().reduce((init, current) => {
                    if (init.length == 0 || init[init.length - 1] !== current) {
                        init.push(current)
                    }
                    return init
                }, [])
            }

### 对象键值对 ###

基本思路：利用了对象的key不可以重复的特性来进行去重。  
但需要注意：

*  无法区分隐式类型转换成字符串后一样的值，比如 1 和 '1'
 *  无法处理复杂数据类型，比如对象（因为对象作为 key 会变成 \[object Object\]）
 *  特殊数据，比如 '**proto**'，因为对象的 **proto** 属性无法被重写

// 解决第一 第三点问题 实现一 test: 111.533935546875ms
            Array.prototype.unique = function () {
                const newArray = []
                const tmp = {}
                for (let i = 0; i < this.length; i++) {
                    if (!tmp[typeof this[i] + this[i]]) {
                        tmp[typeof this[i] + this[i]] = 1
                        newArray.push(this[i])
                    }
                }
                return newArray
            }
    
            // 解决第二点问题 实现二  test: 102.8212890625ms
            Array.prototype.unique = function () {
                const newArray = []
                const tmp = {}
                // debugger
                for (let i = 0; i < this.length; i++) {
                    //使用JSON.stringify() 进行序列化
                    if (!tmp[typeof this[i] + JSON.stringify(this[i])]) {
                        // 将序列化之后作为key来使用
                        tmp[typeof this[i] + JSON.stringify(this[i])] = 1
                        newArray.push(this[i])
                    }
                }
                return newArray
            }

### Map    ###

//test: 20.43896484375ms
            Array.prototype.unique = function () {
                const newArray = [];
                const tmp = new Map();
                for (let i = 0; i < this.length; i++) {
                    if (!tmp.get(this[i])) {
                        tmp.set(this[i], 1);
                        newArray.push(this[i]);
                    }
                }
                return newArray;
            }
    
            // test: 27.573974609375ms
            Array.prototype.unique = function () {
                const tmp = new Map();
                return this.filter(item => {
                    return !tmp.has(item) && tmp.set(item, 1);
                })
            }

### Set ###

//test: 11.35107421875ms
            Array.prototype.unique = function () {
                const set = new Set(this);
                return Array.from(set);
            }
    
            //test: 9.22802734375ms
            Array.prototype.unique = function () {
                return [...new Set(this)];
            }

### 总结 ###

除了考虑时间复杂度外、性能之外，还要考虑数组元素的数据类型（例如下面的例子）等问题权衡选择出采用哪种算法，例如：

const arr = [1, 1, '1', '1', 0, 0, '0', '0', undefined, undefined, null, null, NaN, NaN, {}, {}, [], [], /a/, /a/];

经过综合考虑，最优的数组去重算法是采用Map数据结构实现的算法。

[https_juejin.im_post_6844903608467587085_heading-6]: https://juejin.im/post/6844903608467587085#heading-6