DIV CSS 佈局教程網

陣列去重的五種寫法:從 indexOf 到排序相鄰,效能與取捨一次比較
編輯:關於JavaScript     

陣列去重是面試與實務都常見的小題目,寫法卻有好幾種,效能與適用情境差很多。以下五種由淺入深。

1. 遍歷 + indexOf

最直覺的思路:開一個新陣列,遍歷原陣列,值不在新陣列就放進去。

 // 最簡單的陣列去重法
 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。

2. 物件鍵值對(空間換時間)

速度最快,代價是占用較多記憶體。思路是把值當成物件的鍵,用「鍵是否存在」判斷重複。

 // 速度最快,占空間最多
 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。

3. 索引位置判斷

思路:若目前項在陣列中「第一次出現的位置」不是當前索引,它就是重複的。

 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。

4. 排序後去除相鄰重複

先排序讓相同值相鄰,再遍歷時只收不與前一項相同的。原生 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。

5. 優化版遍歷(推薦)

思路:從右往左找,取得每個值「最右邊的那一次出現」,遇到重複就跳過當前外層迴圈。

 // 思路:取得沒重複的最右一值放入新陣列
 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 往前推,等於直接跳過所有重複項。

indexOf 的 polyfill

 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。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved