DIV CSS 佈局教程網

JavaScript 常用數組算法整理:去重、亂序、交集與差集
編輯:關於JavaScript     

數組操作幾乎是日常開發與面試筆試的必考點。這裡把去重、亂序、類型判斷、交集、並集、差集這幾類常見題型的典型寫法做個彙總,方便查閱。

一、數組去重

方法一,利用 indexOf 判斷是否已存在:

function unique(arr) {
  var result = [];
  for (var i = 0; i < arr.length; i++) {
    if (result.indexOf(arr[i]) == -1) result.push(arr[i]);
  }
  return result;
}

方法二,利用哈希表記錄已出現的值。注意這種寫法可能把字符串 '3' 和數字 3 視為同一個鍵:

function unique(arr) {
  var hash = {}, result = [];
  for (var i = 0; i < arr.length; i++) {
    if (!hash[arr[i]]) {
      hash[arr[i]] = true;
      result.push(arr[i]);
    }
  }
  return result;
}

方法三,排序後比較相鄰元素,同樣存在與方法二類似的類型混淆問題:

function unique(arr) {
  arr.sort();
  var result = [arr[0]];
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] !== arr[i - 1]) {
      result.push(arr[i]);
    }
  }
  return result;
}

方法四,雙層循環逐個比對。效率最低,但不會出現前面兩種方法的類型 bug:

function unique(arr) {
  if (arr.length == 0) return;
  var result = [arr[0]], isRepeate;
  for (var i = 0, j = arr.length; i < j; i++) {
    isRepeate = false;
    for (var k = 0, h = result.length; k < h; k++) {
      if (result[k] === arr[i]) { isRepeate = true; break; }
      if (k == h) break;
    }
    if (!isRepeate) result.push(arr[i]);
  }
  return result;
}

方法五,遞歸配合 indexOf,寫法最為簡潔:

var unique = function (arr, newArr) {
  var num;
  if (-1 == arr.indexOf(num = arr.shift())) newArr.push(num);
  arr.length && unique(arr, newArr);
};

二、數組順序擾亂

方法一,每次隨機抽一個元素搬進新數組:

function shuffle(array) {
  var copy = [], n = array.length, i;
  while (n) {
    i = Math.floor(Math.random() * array.length);
    if (i in array) {
      copy.push(array[i]);
      delete array[i];
      n--;
    }
  }
  return copy;
}

方法二,思路類似,改用 splice 摘除已選項:

function shuffle(array) {
  var copy = [], n = array.length, i;
  while (n) {
    i = Math.floor(Math.random() * n--);
    copy.push(array.splice(i, 1)[0]);
  }
  return copy;
}

方法三,隨機抽到的元素與末尾元素交換,然後末尾前移,這就是經典的 Fisher–Yates 洗牌思路,原地修改、效率更高:

function shuffle(array) {
  var m = array.length, t, i;
  while (m) {
    i = Math.floor(Math.random() * m--);
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }
  return array;
}

三、判斷是否為數組

Array.isArray([]);                       // 方法一:ES5 自帶方法
[] instanceof Array;                     // 方法二:instanceof 運算符
Object.prototype.toString.call([]) === '[object Array]';   // 方法三:toString 返回值

跨 iframe 場景下 instanceof 可能失效,此時 Array.isArray 最可靠。

四、求交集

array1.filter(function (n) { return array2.indexOf(n) != -1; });

五、求並集

原理是連接兩個數組後去重:

function arrayUnique(array, array2) {
  var a = array.concat(array2);
  for (var i = 0; i < a.length; ++i) {
    for (var j = i + 1; j < a.length; ++j) {
      if (a[i] === a[j]) a.splice(j--, 1);
    }
  }
  return a;
}

六、求差集

方法一,只算出「第一個數組相對第二個數組」的差集:

Array.prototype.diff = function (a) {
  return this.filter(function (i) { return a.indexOf(i) < 0; });
};

如果希望把兩個數組互不包含的值都取出來,可以雙向求差後拼接:

var array1 = new Array(55, 55, 88, 6, 68, 109, 55, 33, 6, 2, 1);
var array2 = [55, 88, 99, 69, 109, 55, 33, 6, 2, 1];

var diffArr = array1.concat(array2);
var diff = diffArr.filter(function (i) {
  return array1.indexOf(i) < 0 || array2.indexOf(i) < 0;
});
console.log(diff);

以上就是數組處理中最常用的一批算法模板。實際項目中,若目標環境支持 ES6,filter、reduce、includes、Set 等能力可以讓這些操作寫得更短更直觀——例如用 [...new Set(arr)] 一行完成去重。歡迎在实践中靈活選用,也歡迎補充更多思路。

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