DIV CSS 佈局教程網

JavaScript 陣列操作總整理:計數、差集與五種去重寫法
編輯:關於JavaScript     

陣列是 JavaScript 裡最常用的資料結構,面試也最常從這裡出題。本文整理幾個高頻題型:統計各元素出現次數、求兩陣列差集,以及五種不同的去重實作。

一、統計各數字出現的次數與奇偶

思路是兩段式:先走一遍把不重複的值收集到 res,再用雙層迴圈統計每個值出現了幾次。

var arr = [3,1,2,2,1,3,1];
var sum = [];      // 出現次數
var res = [];      // 不重複的值
var count = 0;

// 收集不重複的值
for (var i = 0; i < arr.length; i++) {
  if (res.indexOf(arr[i]) == -1) { res.push(arr[i]); }
}

// 統計次數
for (var i = 0; i < res.length; i++) {
  for (var j = 0; j < arr.length; j++) {
    if (arr[j] == res[i]) { count++; }
  }
  sum.push(count);
  count = 0;
}

console.log(res);   // [3, 1, 2]

for (var i = 0; i < res.length; i++) {
  var str = (sum[i] % 2 == 0) ? "偶數" : "奇數";
  console.log(res[i] + "出現了" + sum[i] + "次");
  console.log(res[i] + "出現了" + str + "次");
}

這個寫法最好懂,代價是 O(n²) 的時間複雜度。資料量大時,改用物件當雜湊表可以降到接近 O(n)。

二、求兩個陣列的不同元素(阿里筆試題)

function diff(arr1, arr2){
  var ress = [];
  var arr = arr1.concat(arr2);          // 合併後統一檢查

  for (var i = 0, len = arr.length; i < len; i++) {
    if ((arr1.indexOf(arr[i]) >= 0 && arr2.indexOf(arr[i]) < 0) ||
        (arr1.indexOf(arr[i]) < 0  && arr2.indexOf(arr[i]) >= 0)) {
      ress.push(arr[i]);
    }
  }
  return ress;
}

var arr1 = [1,2,3,5,7,6];
var arr2 = [1,2,5];
console.log(diff(arr1, arr2));   // [3, 7, 6]

判斷邏輯是「只在其中一個陣列裡出現」。ES6 之後有個更乾淨的寫法:_.difference 或原生 [...new Set([...a].filter(x => !b.includes(x)))]。

三、陣列去重五種寫法

方法 1|indexOf 判斷,掛在原型上

Array.prototype.unique = function(){
  var arr = [];
  for (var i = 0; i < this.length; i++) {
    if (arr.indexOf(this[i]) == -1) { arr.push(this[i]); }
  }
  return arr;
};
console.log([1,2,3,2,5,6,3].unique());   // [1, 2, 3, 5, 6]

方法 2|用物件當雜湊表

把已經出現過的值記在 n 裡,查詢是 O(1),整體效能比 indexOf 好很多:

Array.prototype.unique = function(){
  var n = {}, r = [];
  for (var i = 0; i < this.length; i++) {
    if (!n[this[i]]) {
      n[this[i]] = true;
      r.push(this[i]);
    }
  }
  return r;
}
console.log([1,2,3,2,5,6,3].unique());   // [1, 2, 3, 5, 6]

方法 3|比較索引位置

如果某元素第一次出現的位置不是目前的 i,就代表它是重複的:

Array.prototype.unique = function(){
  var arr = [this[0]];
  for (var i = 1; i < this.length; i++) {
    if (this.indexOf(this[i]) == i) { arr.push(this[i]); }
  }
  return arr;
}
console.log([1,2,3,4,2,3,4].unique());   // [1, 2, 3, 4]

方法 4|filter 搭配 indexOf

var arr = [4,5,3,2,3,4,5,1];
function fn(num){
  return num.filter(function(item, index, array){
    // indexOf 回傳第一次出現的位置,只有首次出現時才等於 index
    return num.indexOf(item) === index;
  });
}
console.log(fn(arr));   // [4, 5, 3, 2, 1]

方法 5|filter 搭配 hasOwnProperty

function unique(a) {
  var obj = {};
  return a.filter(function(item) {
    return obj.hasOwnProperty(item) ? false : (obj[item] = true);
  });
}
var a = [1, 1, 3, 2, 1, 2, 4];
console.log(unique(a));   // [1, 3, 2, 4]

該選哪一種?

如果只問「最短」,ES6 之後答案是 [...new Set(arr)],一行解決,而且底層就是雜湊實作,效能也是最好的。

上面五種寫法的價值在於理解不同思路:indexOf 依賴線性搜尋,雜湊表用空間換時間,filter 則是把判斷邏輯收攏成一行。另外要提醒,直接擴充 Array.prototype 這件事在正式專案中不建議——它會讓 for...in 的行為變得不可預期,也容易與其他套件的同名方法衝突。改成獨立函式或放到工具物件裡會安全得多。

以上就是 JavaScript 陣列操作的高頻題型整理,包含計數、差集與五種去重實作。

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