前端笔试题——数组去重(保姆级手撕)

引言:

对于传统的前端工程师来说,更多的只是把服务端响应的数据渲染到页面上。

随着前端的不断进化,算法对我们而言也日渐重要,大公司为了优中选优,经常也会用算法题去筛选更优秀的人才。

算法,或许在工作中很少能用到,就算能用到也是直接调现成的库函数,但在求职时却是一个不可忽视的因素,总之机遇和挑战并存吧!

本文是对数组去重这个常规算法题的手撕分析及拓展,希望能够给读者带来无形的财富。

开始:

1.传统数组去重:

传统数组去重,是很硬气的方式,去跟问题硬刚,来完成最直白的数组去重,是种笨办法,但很有效果。

首先,在一个数组中,要对一个数组去重,先想到的一定是让所有元素跟其它元素比较一下,然后删掉相同的。

没错,我也是这么想的,我们反手就是一个嵌套循环

for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
        // 写判断条件
    }
}

这样就构成了i和j双指针联动的形式,可是仔细思考,这好像世界杯足球运动员互相握手的模型

我跟你握手了,这就算完成了,难道你还要再跟我握手吗?

所以,受到启发,我们修改内层循环的初始条件。

for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
        // 写判断条件
    }
}

把j=0,改成j=i+1。这样就有效避免了重复握手的情况。

接着,我们需要判断值是否一样,所以可以比较一下,两个一样的话就删掉内层循环下标的元素。

if (arr[j] === arr[i]) {
   arr.splice(j, 1);
}

注:splice是JS原生语法,需要用数组对象去调用,第一个参数是要调用他的数组需要切掉的下标,第二个参数是往后切几个。

我们加上调用代码:

function arrayOutRepeat(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] === arr[i]) {
                arr.splice(j, 1);
            }
        }
    }
    console.log(arr);
}
arrayOutRepeat([1, 2, 3, 2, 1, 3, 4, 3, 4, 4, 3, 2, 3, 1]);

这样我们就写好了一个算法,我们进行调用试试吧。

结果出现了问题,为什么没有删清楚呢?

原来!我们在splice之后,j就++了,相当于跳过一个元素。

 

 

那我们就让j往回再指一下,让j–,再试试。

 

 

现在正常了,所以上完整代码(手撕终版):

function arrayOutRepeat(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] === arr[i]) {
                arr.splice(j, 1);
                j--;
            }
        }
    }
    return arr;
}
let array = arrayOutRepeat([1, 2, 3, 2, 1, 3, 4, 3, 4, 4, 3, 2, 3, 1]);
console.log(array);

2.排序数组去重:

根据前边的详解,我们大体能够明确传统去重的过程。

我们还可以换种思维,将数组排好序,然后让相邻的元素比较。

这样的代码是非常简单的,也可以说是巧妙解决问题。

function arrayOutRepeat(arr) {
    arr.sort();
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === arr[i + 1]) {
            arr.splice(i, 1);
            i--;
        }
    }
    return arr;
}
let array = arrayOutRepeat([1, 2, 3, 2, 1, 3, 4, 3, 4, 4, 4, 3, 2, 3, 1]);
console.log(array);

3.新数组添加元素:

我们再换种思路,可以声明一个空数组,用新数组比较旧数组,要是没有就添加。

这里使用了indexOf方法,这个方法有一定的兼容性问题,IE低版本慎用!

indexOf方法需要用新数组去调用,参数为旧数组中的第i个元素,返回值如果为-1则表示没有找到。

我们可以利用这一点,去添加旧数组里没有的元素。

function arrayOutRepeat(arr) {
    let arrNew = [];
    for (let i = 0; i < arr.length; i++) {
        if (arrNew.indexOf(arr[i]) == -1) {
            arrNew.push(arr[i]);
        }
    }
    return arrNew;
}
let array = arrayOutRepeat([1, 2, 3, 2, 1, 3, 4, 3, 4, 4, 4, 3, 2, 3, 1]);
console.log(array);

在这里,ES6还有一个includes方法,同样的思路。

function arrayOutRepeat(arr) {
    let arrNew = [];
    for (let i = 0; i < arr.length; i++) {
        if (!arrNew.includes(arr[i])) {
            arrNew.push(arr[i]);
        }
    }
    return arrNew;
}
let array = arrayOutRepeat([1, 2, 3, 2, 1, 3, 4, 3, 4, 4, 4, 3, 2, 3, 1]);
console.log(array);

 

4.拓展:

除了上述三种最常规的去重手段之外,还有不少精简的解决方案,这里简单介绍一下。

I.ES6中Set构造方法:

ES6中的Set是一种集合形式,集合中的元素值是唯一的。

ES6中还对Array新增了一个静态方法Array.from(),可以把Set集合转化成数组形式。

因此配合起来使用,效果更佳,代码量少的可怜。

function arrayOutRepeat(arr) {
    return Array.from(new Set(arr));
}
let array = arrayOutRepeat([1, 2, 3, 2, 1, 3, 4, 3, 4, 4, 4, 3, 2, 3, 1]);
console.log(array);

在arrayOutRepeat方法中,只需要一句代码便解决问题,这个代码已经非常精简了。

可是,还有更精简的方法,真不可思议。

ES6中新增的扩展运算符,可以强制Set集合类型转换成数组,代码量更是少的可怜。

function arrayOutRepeat(arr) {
    return [...new Set(arr)];
}
let array = arrayOutRepeat([1, 2, 3, 2, 1, 3, 4, 3, 4, 4, 4, 3, 2, 3, 1]);
console.log(array);

II.利用Map结构:

Map也是ES6中新加入的内容,是一种用键值对存储数据的结构。

我们可以通过Map实例化的对象map,结合对象调用map封装的API取到key值,再用扩展运算符强制类型转换。

function arrayOutRepeat(arr) {
    let map = new Map();
    for (let i = 0; i < arr.length; i++) {
        if (!map.has(arr[i])) {
            map.set(arr[i])
        }
    }
    return [...map.keys()];
}
let array = arrayOutRepeat([1, 2, 3, 2, 1, 3, 4, 3, 4, 4, 4, 3, 2, 3, 1]);
console.log(array);

III.利用过滤器filter:

过滤器,顾名思义,把不符合条件的滤掉,符合条件的筛出。

其中item是第i项的值,index是索引,而indexOf方法查找方式是顺序查找(从前往后)。

比如遍历到了第二个1的位置,indexOf返回的索引值是第一个1的索引,以此类推。

所以通过比较,加上过滤器,把索引值对不上的全部滤掉,剩下的就是“精英”了。

function arrayOutRepeat(arr) {
    return arr.filter((item, index) => {
        return arr.indexOf(item) === index;
    })
}
let array = arrayOutRepeat([1, 2, 3, 2, 1, 3, 4, 3, 4, 4, 4, 3, 2, 3, 1]);
console.log(array);

IV.递归:

递归在编程中,算是逻辑难度很大的部分。看似代码简洁,其实暗藏玄机。

这里我将网上的代码拆解简化了一下,自己手写一遍就能更清晰!代码如下:

function arrayOutRepeat(arr) {

    arr.sort();

    function loop(index) {
        if (index >= 1) {
            if (arr[index] === arr[index - 1]) {
                arr.splice(index, 1);
            }
            loop(index - 1);
        }
    }
    loop(arr.length - 1);
    return arr;
}

let array = arrayOutRepeat([1, 2, 3, 2, 1, 3, 4, 3, 4, 4, 4, 3, 2, 3, 1]);
console.log(arrayOutRepeat(array));

解析点:

1.思路也是经过排序之后利用索引比较相邻元素的值,进行去留判断。(由后向前)

2.由于形参arr作用域的关系,所以写了个闭包,方便内层函数可以引用外层函数的变量。

3.递归的结束条件,是当index<1时,也就是到首个元素时,递归进行回调。

总结:

以上就是常用的数组去重方法,虽然还有一些组合方法,但基本都是换汤不换药,最重要的是思想!

注:当遇到引用数据类型时(数组,对象等),以上方法无法对他们进行去重处理

这时我们就需要在判断条件,利用instance操作符、isArray方法,constructor属性等去深入判断。

原创地址://www.cnblogs.com/ElemSN/p/13523410.html