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數組去重的必問面試題以及答案的詳細內容了，看完之后是否有所收獲呢？如果想了解更多相關內容，歡迎關注億速云行業資訊！