數組去重幾乎是每場前端面試都會出現的題目。下面用同一份測試數據,逐一實現五種常見思路,並說明它們各自的邊界。
先準備測試數組:
var arr = [1,2,3,3,2,'我','我',34,'我的',NaN,NaN];
思路:建立一個空數組,遍歷原數組,用 indexOf 判斷當前項在臨時數組中是否存在,不存在才 push 進去,最後返回臨時數組。
Array.prototype.removeDuplicate = function(){
var n = [];
for(var i=0;i<this.length;i++){
if(n.indexOf(this[i]) == -1 ){
n.push(this[i]);
}
}
return n;
}
var m = arr.removeDuplicate();
console.log(m);//[1, 2, 3, "我", 34, "我的", NaN, NaN]
注意:這種寫法不會去掉重復的 NaN,因為 NaN === NaN 為 false,indexOf 也找不到它。
思路:遍歷時比較 this.indexOf(this[i]) 與當前下標 i。若相等,說明這是本項在原數組中第一次出現,之前沒有重復值,收進臨時數組;否則跳過。
Array.prototype.removeDuplicate = function(){
var n = [];
for(var i=0;i<this.length-1;i++){
if(this.indexOf(this[i]) == i){
n.push(this[i]);
}
}
return n;
}
var m = arr.removeDuplicate();
console.log(m);//[1, 2, 3, "我", 34, "我的"]
注意:NaN 會被過濾掉,而且循環上界寫成 length-1 會漏掉最後一項,實戰中建議改成 length。
思路:用一個對象當哈希表,遍歷時檢查該屬性是否存在,不存在則標記為 true 並收入結果數組。查表的時間複雜度接近 O(1),是三種命令式寫法裡性能最好的一種。
Array.prototype.removeDuplicate = function(){
var n = [],m = {};
for(var i=0;i<this.length;i++){
if(!m[this[i]]){
m[this[i]] = true;
n.push(this[i]);
}
}
return n;
}
var m = arr.removeDuplicate();
console.log(m);//[1, 2, 3, "我", 34, "我的", NaN]
思路:先對數組排序,讓相同的值挨在一起,再逐一比較當前項與下一項,不相等才收入結果。
Array.prototype.removeDuplicate = function(){
var n = [];
this.sort();
for(var i=0;i<this.length;i++){
if(this[i] != this[i+1]){
n.push(this[i]);
}
}
return n;
}
var m = arr.removeDuplicate();
console.log(m);//[1, 2, 3, 34, NaN, NaN, "我", "我的"]
注意:sort 會直接修改原數組,若不想破壞原數據要先 slice 一份;同時這種寫法不會去掉重復的 NaN。
思路:Set 是一種新的數據結構,可以接收數組或類數組對象,自動去重其中的重復項。再用 Array.from 轉回數組即可。
Array.prototype.removeDuplicate = function(){
return (Array.from(new Set(this)));
}
var m = arr.removeDuplicate();
console.log(m);//[1, 2, 3, "我", 34, "我的", NaN]
這是最簡潔也最推薦的寫法,Set 使用 SameValueZero 演算法比較,能正確處理 NaN,且天然支持對象引用去重。
如果項目允許使用 ES6,直接用 Set;如果必須兼容老浏覽器且數據量較大,選哈希表方案;數據量小、要求可讀性,indexOf 的寫法也夠用。另外提醒一句,直接擴展 Array.prototype 在多人協作項目裡容易造成命名衝突,更穩妥的做法是寫成獨立工具函數。