Js面试题（一）--js实现数组去重怎么实现？

方法1、创建一个新的临时数组来保存数组中已有的元素

方法2、使用哈希表存储已有元素

方法3、使用indexof判断数组元素第一次出现的位置是否为当前位置

方法4、先排序再去重

第一种方法和第三种方法都使用了indexof()，这个函数的执行机制也会遍历数组

第二种使用了哈希表，是最快的

第三种也有一个排序的复杂度的计算

 

详细代码如下：

<!-- js实现数组去重 
    方法1、创建一个新的临时数组来保存数组中已有的元素
    -->
    <!-- js实现数组去重 
    方法2、使用哈希表存储已有元素
    -->
    <!-- js实现数组去重 
    方法3、使用indexof判断数组元素第一次出现的位置是否为当前位置
    -->
    <!-- js实现数组去重 
    方法4、先排序再去重
    -->
    <!-- 随机生成100万个0-1000的数组结果
        方法一执行时间：240
        方法二执行时间：5
        方法三执行时间：477
        方法四执行时间：246
        第三种方法总是第二种方法的将近两倍，而第四种方法与数组的范围有关

        如果是-100的数组
        方法一执行时间：40
        方法二执行时间：4
        方法三执行时间：64
        方法四执行时间：176

        而如果是0-10000
        方法一执行时间：2199
        方法二执行时间：6
        方法三执行时间：4876
        方法四执行时间：298
        第二种方法是最好的，，，但是是以空间换时间
    -->

    <script>
        var a = [];
        for (var i = 0; i < 1000000; i++) {
            a.push(Math.ceil(Math.random() * 10000));
        }
        Array.prototype.unique1 = function() {
            var n = []; //临时数组
            for (var i = 0; i < this.length; i++) {
                //如果当前数组的第i已经保存进了临时数组，那么跳过
                if (n.indexOf(this[i]) == -1) {
                    n.push(this[i]);
                }
            }
            return n;
        }
        Array.prototype.unique2 = function() {
            var hash = [],
                n = []; //hash哈希表，n临时数组
            for (var i = 0; i < this.length; i++) {

                if (!hash[this[i]]) { //如果hash表中没有当前项
                    hash[this[i]] = true; //存入哈希表
                    n.push(this[i]); //当前元素push到临时数组
                }
            }
            return n;
        }
        Array.prototype.unique3 = function() {
            var n = [this[0]];
            for (var i = 1; i < this.length; i++) {
                //如果当前数组元素在数组中出现的第一次的位置不是i
                //说明是重复元素
                if (this.indexOf(this[i]) == i) {
                    n.push(this[i]);
                }
            }
            return n;
        }
        Array.prototype.unique4 = function() {
            this.sort(function(a, b) {
                return a - b;
            });
            var n = [this[0]];
            for (var i = 1; i < this.length; i++) {
                if (this[i] != this[i - 1]) {
                    n.push(this[i]);
                }
            }
            return n;
        }
        var begin1 = new Date();
        a.unique1();
        var end1 = new Date();
        console.log('方法1的执行时间：' + (end1 - begin1));
        var begin2 = new Date();
        a.unique2();
        var end2 = new Date();
        console.log('方法2的执行时间：' + (end2 - begin2));
        var begin3 = new Date();
        a.unique3();
        var end3 = new Date();
        console.log('方法3的执行时间：' + (end3 - begin3));
        var begin4 = new Date();
        a.unique4();
        var end4 = new Date();
        console.log('方法4的执行时间：' + (end4 - begin4));
    </script>

四种方法执行时间如下：

就分享到这些，下次继续···

分享一下我的微信公众号，分享摄影与编程，谢谢大家的关注