數組操作幾乎是日常開發與面試筆試的必考點。這裡把去重、亂序、類型判斷、交集、並集、差集這幾類常見題型的典型寫法做個彙總,方便查閱。
方法一,利用 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)] 一行完成去重。歡迎在实践中靈活選用,也歡迎補充更多思路。