「怎麼去掉陣列裡的重複項」幾乎是前端面試的標準題,百度、騰訊、盛大都出過。題目看起來簡單,但考的其實是你對程式執行方式的理解——同一個功能,用 indexOf、用 hash 表、用排序,效能可能差上好幾倍。
Array.prototype.unique1 = function() {
var n = []; //臨時陣列
for (var i = 0; i < this.length; i++) {
//若當前項已在臨時陣列中則跳過,否則推入
if (n.indexOf(this[i]) == -1) n.push(this[i]);
}
return n;
}
Array.prototype.unique2 = function() {
var n = {}, r = []; //n 為 hash 表,r 為臨時陣列
for (var i = 0; i < this.length; i++) {
if (!n[this[i]]) { //hash 表中沒有當前項
n[this[i]] = true;
r.push(this[i]);
}
}
return r;
}
Array.prototype.unique3 = function() {
var n = [this[0]];
for (var i = 1; i < this.length; i++) {
//若第 i 項第一次出現的位置不是 i,表示它是重複的
if (this.indexOf(this[i]) == i) n.push(this[i]);
}
return n;
}
方法一與方法三都用到 indexOf。這個方法在引擎內部必須逐一走訪直到命中,因此會浪費不少時間。方法二改用雜湊表,以屬性名的方式記錄已出現的值,查表遠比線性搜尋快。
我曾經做過一個測試:產生一萬筆隨機數組成的陣列,分別用這幾種方法跑。結果方法二明顯快於另外兩種。代價是它多了一個 hash 表,記憶體佔用較高——這就是典型的空間換時間。
Array.prototype.unique4 = function() {
this.sort();
var re = [this[0]];
for (var i = 1; i < this.length; i++) {
if (this[i] !== re[re.length - 1]) re.push(this[i]);
}
return re;
}
思路是先排序,讓相同的值相鄰,再逐一比較。排序用的是原生 sort(引擎內部多為快速排序)。實測執行時間約為方法二的三倍,但仍比方法一、三快。要注意 sort() 會直接改動原陣列,若不想影響外部資料,先 slice() 複製一份。
做搜尋歷史記錄功能時也會用到。原本直接用 indexOf,但這個方法在 ECMAScript 5 才有,IE8 及以下不支援,因此可以自己補一個:
Array.prototype.unique = function(){
var length = this.length;
if (length <= 1) { return this; }
if (!Array.prototype.indexOf) {
Array.prototype.indexOf = function(item){
var l = this.length, i = 0, r = -1;
if (l <= 0) { return -1; }
for (; i < l; i++) {
if (this[i] === item) { r = i; }
}
return r;
}
}
var result = [];
for (var i = 0; i < length; i++) {
if (result.indexOf(this[i]) === -1) result.push(this[i]);
}
return result;
}
function unique(arr) {
var result = [], isRepeated;
for (var i = 0, len = arr.length; i < len; i++) {
isRepeated = false;
for (var j = 0, len2 = result.length; j < len2; j++) {
if (arr[i] == result[j]) { isRepeated = true; break; }
}
if (!isRepeated) result.push(arr[i]);
}
return result;
}
思路是把元素一個個搬到新陣列,搬運時檢查是否重複。從巢狀迴圈就能看出它效率極低,時間複雜度是 O(n²)。改善方式正是方法二的思路:用雜湊結構記錄已有元素,省掉內層迴圈。
雜湊法(方法二)在多數情況下最快,缺點是遇到物件時會把 [object Object] 當成同一個鍵,造成誤判;排序法(方法四)不改變元素型別判斷方式但會動到原陣列;暴力法只適合小陣列。
如果是現代環境,其實不必自己寫:[...new Set(arr)] 一行就能完成,而且 Set 使用 SameValueZero 演算法,連 NaN 也能正確視為同一值。若要自訂比較邏輯(例如依 id 去重物件),則用 filter 搭配一個 Map 記錄看過的鍵會最清楚。