原创 Java面试题答疑解惑之数组去重

数组去重是Java面试者常常会遇到的面试题之一。不知道大家有没有想过，为什么面试官总是喜欢询问求职者这个问题？其实，关于数组去重的问题表面上看起来并不难，但是通过面试者对相关问题的回答，可以充分检验出面试者的Java能力水平究竟如何，以及对于考虑问题的思维方式够不够全面。因此，大家千万别觉得面试官问你数组去重的问题，就只是一个简单的问题，其实在背后有着更多的考量。
　　

 

1、你知道多少种去重方式？
　　

（1）双层 for 循环：双重 for 循环是比较笨拙的方法，它实现的原理很简单：先定义一个包含原始数组第一个元素的数组，然后遍历原始数组，将原始数组中的每个元素与新数组中的每个元素进行比对，如果不重复则添加到新数组中，最后返回新数组；因为它的时间复杂度是O(n^2)，如果数组长度很大，效率会很低。代码如下：
　　

function distinct(arr) {
　　

for (let i=0, len=arr.length; i<len; i++) {
　　

for (let j=i+1; j<len; j++) {
　　

if (arr[i] == arr[j]) {
　　

arr.splice(j, 1);
　　

// splice 会改变数组长度，所以要将数组长度 len 和下标 j 减一
　　

len--;
　　

j--;
　　

}

}

}
　　

return arr;
　　

}
　　

（2）Array.filter() 加 indexOf：利用indexOf检测元素在数组中第一次出现的位置是否和元素现在的位置相等，如果不等则说明该元素是重复元素。代码如下：
　　

function distinct(a, b) {
　　

let arr = a.concat(b);
　　

return arr.filter((item, index)=> {
　　

return arr.indexOf(item) === index
　　

})
　

}
　　

（3）Array.sort() 加一行遍历冒泡：调用了数组的排序方法 sort()，V8引擎 的 sort() 方法在数组长度小于等于10的情况下，会使用插入排序，大于10的情况下会使用快速排序。然后，根据排序后的结果进行遍历及相邻元素比对(其实就是一行冒泡排序比较)，如果相等则跳过该元素，直到遍历结束。
　　

function distinct(array) {
　　

var res = [];
　　

var sortedArray = array.concat().sort();
　　

var seen;
　　

for (var i = 0, len = sortedArray.length; i < len; i++) {
　　

// 如果是第一个元素或者相邻的元素不相同
　　

if (!i || seen !== sortedArray[i]) {
　　

res.push(sortedArray[i])
　　

}
　　

seen = sortedArray[i];
　　

}
　　

return res;
　　

}
　　

（4）ES6 中的 Set 去重：ES6 提供了新的数据结构 Set，Set 结构的一个特性就是成员值都是唯一的，没有重复的值。
　　

（5）Object 键值对：这种方法是利用一个空的 Object 对象，我们把数组的值存成 Object 的 key 值，比如 Object[value1] = true，在判断另一个值的时候，如果 Object[value2]存在的话，就说明该值是重复的。代码如下：

function distinct(array) {
　　

var obj = {};
　　

return array.filter(function(item, index, array){
　　

return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true)
　　

})
　　

}
　　

2、以上解法的性能排名。
　　

双重 for 循环 > Array.filter()加 indexOf > Array.sort() 加一行遍历冒泡 > ES6中的Set去重 > Object 键值对去重复
　　

3、去重复过程中，是想要空间复杂度最低吗？
　　

以上的所有数组去重方式，应该 Object 对象去重复的方式是时间复杂度是最低的，除了一次遍历时间复杂度为O(n) 后，查找到重复数据的时间复杂度是O(1)，类似散列表，大家也可以使用 ES6 中的 Map 尝试实现一下。
　　

但是对象去重复的空间复杂度是最高的，因为开辟了一个对象，其他的几种方式都没有开辟新的空间，从外表看来，更深入的源码有待探究，这里只是要说明大家在回答的时候也可以考虑到时间复杂度还有空间复杂度。
　　

另外补充一个误区，有的小伙伴会认为 Array.filter()加 indexOf 这种方式时间复杂度为 O(n) ,其实不是这样，我觉得也是O(n^2)。因为 indexOf 函数，源码其实它也是进行 for 循环遍历的。具体实现如下
　　

String.prototype.indexOf = function(s) {
　　

for (var i = 0; i < this.length - s.length; i++) {
　　

if (this.charAt(i) === s.charAt(0) &&
　　

this.substring(i, s.length) === s) {
　　

return i;
　　

}
　　

}
　　

return -1;
　　

};
　　

4、lodash如何实现去重
　　

lodash的uniq方法的源码实现。这个方法的行为和使用Set进行去重的结果一致。当数组长度大于等于200时，会创建Set并将Set转换为数组来进行去重（Set不存在情况的实现不做分析）。当数组长度小于200时，会使用类似前面提到的双重循环的去重方案，另外还会做NaN的去重。

以上就是关于数组去重的相关Java面试题答疑解惑。总的来说，面试前一定要做好充足的准备，这样才能在面试中充分发挥出自己的应有水平。