引言：對于傳統(tǒng)的前端工程師來說，更多的只是把服務端響應的數(shù)據(jù)渲染到頁面上。 隨著前端的不斷進化，算法對我們而言也日漸重要，大公司為了優(yōu)中選優(yōu)，經(jīng)常也會用算法題去篩選更優(yōu)秀的人才。 算法，或許在工作中很少能用到，就算能用到也是直接調(diào)現(xiàn)成的庫函數(shù)，但在求職時卻是一個不可忽視的因素，總之機遇和挑戰(zhàn)并存吧！ 本文是對數(shù)組去重這個常規(guī)算法題的手撕分析及拓展，希望能夠給讀者帶來無形的財富。 開始：1.傳統(tǒng)數(shù)組去重：傳統(tǒng)數(shù)組去重，是很硬氣的方式，去跟問題硬剛，來完成最直白的數(shù)組去重，是種笨辦法，但很有效果。 首先，在一個數(shù)組中，要對一個數(shù)組去重，先想到的一定是讓所有元素跟其它元素比較一下，然后刪掉相同的。
沒錯，我也是這么想的，我們反手就是一個嵌套循環(huán)： for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { // 寫判斷條件 }
}這樣就構成了i和j雙指針聯(lián)動的形式，可是仔細思考，這好像世界杯足球運動員互相握手的模型。 我跟你握手了，這就算完成了，難道你還要再跟我握手嗎？ 所以，受到啟發(fā)，我們修改內(nèi)層循環(huán)的初始條件。 for (let i = 0; i < arr.length; i++) { for (let j = i + 1; j < arr.length; j++) { // 寫判斷條件 }
}把j=0，改成j=i+1。這樣就有效避免了重復握手的情況。 接著，我們需要判斷值是否一樣，所以可以比較一下，兩個一樣的話就刪掉內(nèi)層循環(huán)下標的元素。 if (arr[j] === arr[i]) {
arr.splice(j, 1);
}注：splice是JS原生語法，需要用數(shù)組對象去調(diào)用，第一個參數(shù)是要調(diào)用他的數(shù)組需要切掉的下標，第二個參數(shù)是往后切幾個。 我們加上調(diào)用代碼： 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]);這樣我們就寫好了一個算法，我們進行調(diào)用試試吧。
結果出現(xiàn)了問題，為什么沒有刪清楚呢？ 原來！我們在splice之后，j就++了，相當于跳過一個元素。
那我們就讓j往回再指一下，讓j--，再試試。
現(xiàn)在正常了，所以上完整代碼（手撕終版）： 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.排序數(shù)組去重：根據(jù)前邊的詳解，我們大體能夠明確傳統(tǒng)去重的過程。 我們還可以換種思維，將數(shù)組排好序，然后讓相鄰的元素比較。 這樣的代碼是非常簡單的，也可以說是巧妙解決問題。 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.新數(shù)組添加元素：我們再換種思路，可以聲明一個空數(shù)組，用新數(shù)組比較舊數(shù)組，要是沒有就添加。 這里使用了indexOf方法，這個方法有一定的兼容性問題，IE低版本慎用！ indexOf方法需要用新數(shù)組去調(diào)用，參數(shù)為舊數(shù)組中的第i個元素，返回值如果為-1則表示沒有找到。 我們可以利用這一點，去添加舊數(shù)組里沒有的元素。 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.拓展：除了上述三種最常規(guī)的去重手段之外，還有不少精簡的解決方案，這里簡單介紹一下。 I.ES6中Set構造方法：ES6中的Set是一種集合形式，集合中的元素值是唯一的。 ES6中還對Array新增了一個靜態(tài)方法Array.from()，可以把Set集合轉(zhuǎn)化成數(shù)組形式。 因此配合起來使用，效果更佳，代碼量少的可憐。 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方法中，只需要一句代碼便解決問題，這個代碼已經(jīng)非常精簡了。 可是，還有更精簡的方法，真不可思議。 ES6中新增的擴展運算符，可以強制Set集合類型轉(zhuǎn)換成數(shù)組，代碼量更是少的可憐。 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中新加入的內(nèi)容，是一種用鍵值對存儲數(shù)據(jù)的結構。 我們可以通過Map實例化的對象map，結合對象調(diào)用map封裝的API取到key值，再用擴展運算符強制類型轉(zhuǎn)換。 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.遞歸：遞歸在編程中，算是邏輯難度很大的部分?？此拼a簡潔，其實暗藏玄機。 這里我將網(wǎng)上的代碼拆解簡化了一下，自己手寫一遍就能更清晰！代碼如下： 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.思路也是經(jīng)過排序之后利用索引比較相鄰元素的值，進行去留判斷。（由后向前） 2.由于形參arr作用域的關系，所以寫了個閉包，方便內(nèi)層函數(shù)可以引用外層函數(shù)的變量。 3.遞歸的結束條件，是當index<1時，也就是到首個元素時，遞歸進行回調(diào)。 總結：以上就是常用的數(shù)組去重方法，雖然還有一些組合方法，但基本都是換湯不換藥，最重要的是思想！ 注：當遇到引用數(shù)據(jù)類型時（數(shù)組，對象等），以上方法無法對他們進行去重處理。 這時我們就需要在判斷條件，利用instance操作符、isArray方法，constructor屬性等去深入判斷。 |
|
|
