Java數(shù)組去重面試題和答案

這篇文章給大家分享的是有關(guān)Java數(shù)組去重的必問面試題以及答案。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考。一起跟隨小編過來看看吧。　　

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

（1）雙層 for 循環(huán)：雙重 for 循環(huán)是比較笨拙的方法，它實(shí)現(xiàn)的原理很簡(jiǎn)單：先定義一個(gè)包含原始數(shù)組第一個(gè)元素的數(shù)組，然后遍歷原始數(shù)組，將原始數(shù)組中的每個(gè)元素與新數(shù)組中的每個(gè)元素進(jìn)行比對(duì)，如果不重復(fù)則添加到新數(shù)組中，最后返回新數(shù)組；因?yàn)樗臅r(shí)間復(fù)雜度是O(n^2)，如果數(shù)組長(zhǎng)度很大，效率會(huì)很低。代碼如下：
　　

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 會(huì)改變數(shù)組長(zhǎng)度，所以要將數(shù)組長(zhǎng)度 len 和下標(biāo) j 減一
　　

len--;
　　

j--;
　　

}

}

}
　　

return arr;
　　

}
　　

（2）Array.filter() 加 indexOf：利用indexOf檢測(cè)元素在數(shù)組中第一次出現(xiàn)的位置是否和元素現(xiàn)在的位置相等，如果不等則說明該元素是重復(fù)元素。代碼如下：
　　

function distinct(a, b) {
　　

let arr = a.concat(b);
　　

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

return arr.indexOf(item) === index
　　

})
　

}
　　

（3）Array.sort() 加一行遍歷冒泡：調(diào)用了數(shù)組的排序方法 sort()，V8引擎 的 sort() 方法在數(shù)組長(zhǎng)度小于等于10的情況下，會(huì)使用插入排序，大于10的情況下會(huì)使用快速排序。然后，根據(jù)排序后的結(jié)果進(jìn)行遍歷及相鄰元素比對(duì)(其實(shí)就是一行冒泡排序比較)，如果相等則跳過該元素，直到遍歷結(jié)束。
　　

function distinct(array) {
　　

var res = [];
　　

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

var seen;
　　

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

// 如果是第一個(gè)元素或者相鄰的元素不相同
　　

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

res.push(sortedArray[i])
　　

}
　　

seen = sortedArray[i];
　　

}
　　

return res;
　　

}
　　

（4）ES6 中的 Set 去重：ES6 提供了新的數(shù)據(jù)結(jié)構(gòu) Set，Set 結(jié)構(gòu)的一個(gè)特性就是成員值都是唯一的，沒有重復(fù)的值。
　　

（5）Object 鍵值對(duì)：這種方法是利用一個(gè)空的 Object 對(duì)象，我們把數(shù)組的值存成 Object 的 key 值，比如 Object[value1] = true，在判斷另一個(gè)值的時(shí)候，如果 Object[value2]存在的話，就說明該值是重復(fù)的。代碼如下：

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 循環(huán) > Array.filter()加 indexOf > Array.sort() 加一行遍歷冒泡 > ES6中的Set去重 > Object 鍵值對(duì)去重復(fù)
　　

3、去重復(fù)過程中，是想要空間復(fù)雜度最低嗎？
　　

以上的所有數(shù)組去重方式，應(yīng)該 Object 對(duì)象去重復(fù)的方式是時(shí)間復(fù)雜度是最低的，除了一次遍歷時(shí)間復(fù)雜度為O(n) 后，查找到重復(fù)數(shù)據(jù)的時(shí)間復(fù)雜度是O(1)，類似散列表，大家也可以使用 ES6 中的Map嘗試實(shí)現(xiàn)一下。
　　

但是對(duì)象去重復(fù)的空間復(fù)雜度是最高的，因?yàn)殚_辟了一個(gè)對(duì)象，其他的幾種方式都沒有開辟新的空間，從外表看來，更深入的源碼有待探究，這里只是要說明大家在回答的時(shí)候也可以考慮到時(shí)間復(fù)雜度還有空間復(fù)雜度。
　　

另外補(bǔ)充一個(gè)誤區(qū)，有的小伙伴會(huì)認(rèn)為 Array.filter()加 indexOf 這種方式時(shí)間復(fù)雜度為 O(n) ,其實(shí)不是這樣，我覺得也是O(n^2)。因?yàn)?indexOf 函數(shù)，源碼其實(shí)它也是進(jìn)行 for 循環(huán)遍歷的。具體實(shí)現(xiàn)如下
　　

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如何實(shí)現(xiàn)去重
　　

lodash的uniq方法的源碼實(shí)現(xiàn)。這個(gè)方法的行為和使用Set進(jìn)行去重的結(jié)果一致。當(dāng)數(shù)組長(zhǎng)度大于等于200時(shí)，會(huì)創(chuàng)建Set并將Set轉(zhuǎn)換為數(shù)組來進(jìn)行去重（Set不存在情況的實(shí)現(xiàn)不做分析）。當(dāng)數(shù)組長(zhǎng)度小于200時(shí)，會(huì)使用類似前面提到的雙重循環(huán)的去重方案，另外還會(huì)做NaN的去重。

以上就是Java數(shù)組去重的必問面試題以及答案的詳細(xì)內(nèi)容了，看完之后是否有所收獲呢？如果想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊！