題目:寫一個函式去掉陣列中的重複值。傳入 [0, 8, 5, 4, 78, 8, 90, 4, 'a', 'b', 'a'],要求回傳 [0, 4, 5, 8, 78, 90, 'a', 'b']。
這題看起來簡單,但要在「不破壞原陣列」與「時間複雜度低」之間取得平衡,其實需要一點想法。
先把陣列排序,再逐一刪掉相鄰的相同元素。問題是排序會改變原陣列的順序,元素的「原有屬性」被破壞了,不符合題目要求,直接放棄。
建立新陣列 b,把 a 的元素一個個 push 進去,但 push 之前先檢查該元素是否已存在。這是最直覺也最笨的作法,時間複雜度 n²,資料量大時會很慢。
關鍵洞察是:JavaScript 物件的屬性查找接近 O(1),而屬性名不可能重複。於是可以用一個空物件當「已出現過的集合」:
var getNR = function (src) {
src = src || [];
var res = {};
var curr = [];
var i, j = 0, temp, name;
for (i = 0; i < src.length; i++) {
temp = src[i];
if (res[temp]) {
// 已存在,甚麼都不做
} else {
res[temp] = 1;
}
}
for (name in res) {
if (res.hasOwnProperty(name)) {
curr[j++] = name;
}
}
return curr;
};
整體流程是兩趟:第一趟把元素當屬性名塞進物件(重複的自然被吸收),第二趟用 for...in 把屬性名依序撈回陣列。用 hasOwnProperty 過濾是為了排除原型鏈上的屬性。
1 與 '1' 會被視為同一個;[1,2] 與 '1,2' 也會撞在一起。對純數字陣列沒問題,混合型別就要小心。res[temp] 為 falsy 的判斷對某些值不準確,建議改用 hasOwnProperty 判斷存在性。[0,4,5,8,78,90,a,b] 而不是原始順序。// ES6 Set,簡短且保序
var arr = [0, 8, 5, 4, 78, 8, 90, 4, 'a', 'b', 'a'];
var unique = [...new Set(arr)];
// 或用 filter + indexOf
var unique2 = arr.filter(function (v, i) { return arr.indexOf(v) === i; });
Set 版本時間複雜度 O(n)、保留原始順序、型別判斷正確,是目前的首選。
變種題目要求「在 Array 類別上新增一個方法,任何陣列呼叫後都能去重」。這題除了去重本身,還考驗對 prototype 與 this 的理解:
Array.prototype.unique = function () {
var seen = {};
var result = [];
for (var i = 0; i < this.length; i++) {
var key = typeof this[i] + ':' + this[i]; // 加上型別前綴避免碰撞
if (!seen[key]) { seen[key] = true; result.push(this[i]); }
}
return result;
};
不過要提醒:擴充內建原型容易與第三方套件或其他開發者的實作衝突,實務上建議定義成獨立工具函式,而非掛在 Array.prototype 上。