陣列是 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 陣列操作的高頻題型整理,包含計數、差集與五種去重實作。