陣列去重是面試與實務都常見的小題目,寫法卻有好幾種,效能與適用情境差很多。以下五種由淺入深。
最直覺的思路:開一個新陣列,遍歷原陣列,值不在新陣列就放進去。
// 最簡單的陣列去重法
function unique1(array){
var n = []; // 暫存結果
for(var i = 0; i < array.length; i++){
// 若目前項已存在於 n 中則跳過,否則推入
if (n.indexOf(array[i]) == -1) n.push(array[i]);
}
return n;
}
注意:indexOf 是 ECMAScript 5 的方法,IE8 及以下不支援,需自行補 polyfill。
速度最快,代價是占用較多記憶體。思路是把值當成物件的鍵,用「鍵是否存在」判斷重複。
// 速度最快,占空間最多
function unique2(array){
var n = {}, r = [], len = array.length, val, type;
for (var i = 0; i < array.length; i++) {
val = array[i];
type = typeof val;
if (!n[val]) {
n[val] = [type];
r.push(val);
} else if (n[val].indexOf(type) < 0) {
n[val].push(type);
r.push(val);
}
}
return r;
}
陷阱:物件鍵會被自動 toString(),於是 1 與 "1"、以及 {} 與 {} 都可能互相混淆。原始碼用型別陣列緩解了部分問題,但物件型別仍然無法正確區分,需要更嚴謹的比較時还是得回到 indexOf。
思路:若目前項在陣列中「第一次出現的位置」不是當前索引,它就是重複的。
function unique3(array){
var n = [array[0]]; // 先放入第一項
for(var i = 1; i < array.length; i++) {
if (array.indexOf(array[i]) == i) n.push(array[i]);
}
return n;
}
效能與方法 1 相當,同樣依賴 indexOf。
先排序讓相同值相鄰,再遍歷時只收不與前一項相同的。原生 sort 的結果在數字上並不直觀(預設是字串比較),但若不講究順序,這缺點不影響。
function unique4(array){
array.sort();
var re = [array[0]];
for(var i = 1; i < array.length; i++){
if ( array[i] !== re[re.length - 1] ){
re.push(array[i]);
}
}
return re;
}
注意它會改動原陣列;若不希望有副作用,先 array.slice().sort()。數字排序請傳入比較函式 (a, b) => a - b。
思路:從右往左找,取得每個值「最右邊的那一次出現」,遇到重複就跳過當前外層迴圈。
// 思路:取得沒重複的最右一值放入新陣列
function unique5(array){
var r = [];
for(var i = 0, l = array.length; i < l; i++) {
for(var j = i + 1; j < l; j++)
if (array[i] === array[j]) j = ++i;
r.push(array[i]);
}
return r;
}
程式碼簡短,實作卻巧妙:內層一旦找到相同值,就把外層索引 i 往前推,等於直接跳過所有重複項。
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;
};
}
ES6 之後,去重已經是標準語法:
var arr = [2,2,3,3,4,5,6,7,7];
// 方式一:Set
var unique = [...new Set(arr)];
// 或 Array.from(new Set(arr))
// 方式二:filter
var unique2 = arr.filter((v, i, self) => self.indexOf(v) === i);
// 物件陣列依指定欄位去重
var list = [{id:1},{id:2},{id:1}];
var byId = [...new Map(list.map(o => [o.id, o])).values()];
Set 的優點是它能正確區分型別(1 與 "1" 視為不同),也能容納 NaN 與物件參照,比鍵值對法可靠得多,時間複雜度也只有 O(n)。上面五種寫法值得理解,但新專案請直接用 Set。