面試前複習 JavaScript,無可避免會撞上陣列去重這一題。本文把自己整理的四種思路完整記錄下來,包含各自的優缺點與踩過的坑。這個系列不預定篇數、也不保證時效,想到哪寫到哪,純粹談個人理解,若有錯誤歡迎指正。
陣列去重是演算法考察的熱門題目,實現方式大致可分兩條路:唯一性與非唯一性。講白了就是「挑出只出現一次的」或「刪掉重複出現的」。以下演算法名稱都是我自己隨便取的,請忽略命名。
顧名思義:把陣列裡每個元素都拿去跟「已存放元素的結果陣列」比一遍,遇到沒出現過的就放進去,直到掃完為止。因為外層與內層都有迴圈,也可以叫雙循環匹配去重——這大概是所有人第一時間都能想到的做法。
var arr = [1, 3, 4, 56, 3, 7, 9, 7];
var result = [];
// 比對是否已存在
function isMatch(array, n) {
for (var i = 0; i < array.length; i++) {
if (array[i] === n) {
return true;
}
}
return false;
}
// 逐一驗證所有元素
function unqiue(array) {
for (var i = 0; i < array.length; i++) {
if (!isMatch(result, array[i])) {
result.push(array[i]);
}
}
return result;
}
console.log(unqiue(arr));
這裡有個容易忽略的 bug:如果陣列裡同時存在數字 1 和字串 '1',用雙等號 == 比較時瀏覽器會做型別轉換,兩者會被誤判為同一個值。改用全等 === 才是正確的:
var arr = [1, 3, 4, 56, 3, '1', 7, 9, 7]; // isMatch 內改用 array[i] === n,即可正確保留 '1'
優點:實作簡單、思路直觀。缺點:效率低落,時間複雜度 O(n²)。
原理是利用 Object 的鍵具有唯一性:把陣列元素轉成物件的 key,值存索引,最後用 for...in 把 key 收集回新陣列。由於 Array、JSON 與 {} 本質上都是 Object,三種寫法效果完全相同。
var arr = [1, 3, 4, 56, 3, '1', 7, 9, 7];
function unqiue(array) {
var cache = {}; // 也可以寫成 [] 或 new Object()
var result = [];
// 把元素當成物件的 key
for (var i = 0; i < array.length; i++) {
cache[array[i]] = i;
}
// key 就是去重後的元素
for (var key in cache) {
result.push(key);
}
return result;
}
console.log(unqiue(arr));
優點:簡單,效率非常高。缺點:一是改變了元素型別——物件的 key 一律是字串,原本的數字 1 出來會變成 '1';二是無法區分數字與數字形式的字串,兩者會被視為同一個鍵。
思路是先把陣列排序成升序或降序的「隊列」,這樣相同的值自然就挨在一起;然後從尾端往前逐一比對,若與前一格相同就刪掉尾端,再繼續往前。全部掃完,剩下的就是去重後的結果。
var arr = [6, 4, 6, 9, '6', 13, 56, 9, '11', 1, 8, '7', 17, 5, 45, 3, 7];
function unqiue(array) {
// 排序,讓相同元素相鄰
array.sort(function (m, n) { return m - n; });
// 從隊尾往前比,相同就刪除
function loop(index) {
if (index >= 1) {
if (array[index] === array[index - 1]) {
array.splice(index, 1);
}
loop(index - 1);
}
}
loop(array.length - 1);
return array;
}
console.log(unqiue(arr));
優點:效率較高。缺點:不是最快,而且會破壞原始陣列(sort 是原地排序),若原陣列還要繼續使用,記得先 slice() 複製一份。另外遞迴深度等於陣列長度,資料量大時有堆疊溢出的風險,改成迴圈更安全。
indexOf 是 ECMAScript 5 新增的方法,IE8 及以下不支援(IE8 只實作了部分 ES5),因此在需要相容舊環境時得自己補一個:
if (!Array.prototype.indexOf) {
Array.prototype.indexOf = function (item) {
var result = -1, a_item = null;
if (this.length == 0) {
return result;
}
for (var i = 0, len = this.length; i < len; i++) {
a_item = this[i];
if (a_item === item) {
result = i;
break;
}
}
return result;
};
}
有了 indexOf,去重就能寫得非常短:
function unique(array) {
return array.filter(function (el, index, arr) {
return index === arr.indexOf(el); // 只保留第一次出現的位置
});
}
優點:程式碼極簡。缺點:每個元素都要做一次線性搜尋,整體仍是 O(n²)。
把上面的分析攤開來看,結論其實很清楚:
若目標環境允許 ES6,[...new Set(arr)] 一行就解決,而且 Set 能正確區分 1 與 '1',也能存放物件參照,語意最乾淨。
若必須相容舊瀏覽器,物件字典法在效能與簡潔度之間最平衡,唯一要記住的是型別會被轉為字串;若元素是物件,就不能直接當 key,得改用「以唯一識別欄位(如 id)組字串當鍵」或 filter + indexOf 搭配自訂比較。
至於雙層迴圈與排序遞歸,效能都不理想,主要價值在於面試時展現思路,以及理解「用空間換時間」這個基本取捨。
最後補一個所有方法都適用的提醒:去重前先確認需求是「保留第一次出現」還是「保留最後一次」,以及要不要保持原始順序。物件字典法與排序法的輸出順序都和原陣列不同,若順序有意義(例如時間序列資料),記得額外處理。