前言

面试中被经常问及的和算法相关的基础问题，就是关于数组的，比如数组去重，取最大最小值，排序，洗牌等等。关于数组的很多操作，比如 splice, slice, sort, reverse, concat, push, pop, unshift, shift 等等也都会被问及。还有就是关于高级函数，比如 filter, forEach, map, some, every 等等。今天主要谈谈数组的去重问题。

对于数组去重，最开始接触的一个题目是这样的：

var arr = [ ‘h’, ‘e’, ‘l’, ‘l’, ‘o’, ‘w’, ‘o’, ‘r’, ‘l’, ‘d’ ];

找到数组中出现次数最多的字母，并给出个数和每一个所在的位置

因为当时是刚开始接触编程，所以对于这类题目完全不知道如何下手，更不知道什么是所谓的算法和数据结构。我已经不记得当时我是如何解决这道题了，但是只是记得老师给的建议是说我的方法太复杂了，然后给了一个将数组转化成 hash 的方式解决的。当时我看到这种解法之后觉得实在是太精妙了，所以一下就记住了。后来很多的问题我都是通过转化成 hash 的方式解决的。但是慢慢地，随着对计算机的了解，才知道原来这就是算法，然后就了解了更多的算法方面的内容。尤其是排序，学习了冒泡排序和快排两种算法之后，对于这两种算法的理解就更加深刻了。并且在学习 coursera 的 python for everybody 的过程中，Dr Chunk 通过 ppt 的形式，非常巧妙的讲解了数组求最大值、最小值的过程，所以对于求最大最小值也理解的更加深刻了。

为什么这次又来谈去重这件事情呢？其实有很多原因共同促成的。首先，前两天的面试过程中，是有去重的；我使用了 hash 的方式，还有之前在一个国外博客上面发现的 filter 的方法。其次，在这个面试之前，我当时为了练习，使用了双重循环的方式也实现了去重。所以，这么多方法，有必要总结一下。其次，面试回来结束之后，我又 google 了一下 JS 去重的实现，在 SO 上也找到了很多相关的内容。发现还有很多种实现方式，所以需要把这些内容做一个整理，并记录下来。最后，你会发现每种方法都会其局限性，很多时候面试官对于去重的实现问的比较浅，如果深究的话其实里面还是有很多特殊的情况是这些方法解决不了的。比如数组的元素是对象等等。

方法

一个一个说，先从最基本的开始。

双重循环

for (var i = 0; i < arr.length; i++) {
    for (var j = i+1; j < arr.length; j++) {
        if (arr[i] === arr[j]) {
            arr.splice(j, j+1);
        }
    }
}

这种方法，就是从头开始，固定一个数组的元素，然后遍历后面所有的元素，如果找到和这个元素相同的元素，则通过 splice() 方法将这个重复元素从 arr 中删除，然后再固定第二个元素，遍历从这个元素后面的元素，找到相同的，则删除。如此循环一遍，自然数组中就肯定没有相同的元素了，实现了去重。这两面有两件事情需要说明一下。

1. 循环内部嵌套循环可以从上一层循环开始，而不是完全重新开始，因为上一层循环之前的内容是都满足条件的。不会有重复的元素，但是如果需要的话，其实也会可以的。只不过增加了复杂度。
2. splice() 方法可以删除元素。

一个比较讨巧的方法

arr.filter(function(item, index, arr) {
    return arr.indexOf(item) == index;
})

// 或者用 ES6 的写法写出来
arr.filter((item, index, arr) => arr.indexOf(item) === index)

这种方式就是保证元素是第一次出现，如果不是那么就被过滤掉了。或者说，第一个出现的元素不会被过滤掉，因为 arr.indexOf(item) == index 肯定为真，但是如果第二次出现同样的元素的时候，因为上述表达式为 false，那么自然就被过滤掉，返回的数组自然就是没有重复元素的数组。这里面用到了数组的 filter 方法。还有就是注意 ES6 的箭头函数的写法，没有用到 return 关键词，直接写表达式，就自动会作为返回值。

转化成 hash

说是转化成 hash，其实在 JS 中就是相当于转化成 object。只不过有不同的叫法而已，也可以叫 map 或者 dictionary 等等。

var obj = {};
for (var i = 0; i < arr.length; i++) {
    var currentEle = arr[i];
    if( obj[currentEle] == undefined ) {
        obj[currentEle] == [];
    } 
    obj[currentEle].push(i)
}
newArr = Object.keys(obj); // 获取的就是去重后的数组
同时这个 obj 的每一个 key/value pair 而言，key 是出现的元素，而 value 则是出现的元素的位置组成的数组，可以通过获取数组的 length 来知道出现的次数，而位置则是数组中的该元素出现的位置。

这个方法有很多变种，但是大概的思路都是这样的。主要是转化成数组的话可以知道这个元素出现的位置，如果转化成数字 1， 然后每次都加 1 的话，可以知道出现的次数。

但是这种方式最大的问题在于，如果数组是有数字的话，返回的去重数组中数组转化为了字符串，比如 [1, 2, 3, 2, 1] 去重后得到的是 [‘1’, ‘2’, ‘3’]

Set() 实现

[…new Set(arr)]

这种方法是 ES6 的解决方式。目前对 set 还不是很了解，所以先不评论。

结语

关于去重，大概就总结这么一些方法。但是还有很多方法，都是类似的。可以在 google 搜索 js uniq 就会出现很多不错的方式。下面是我参考的一些内容

http://stackoverflow.com/questions/1960473/unique-values-in-an-array
http://stackoverflow.com/questions/840781/easiest-way-to-find-duplicate-values-in-a-javascript-array