去重是前端面試的常客,也是資料處理時的實際需求。本文把常見做法從最直觀的雙層迴圈一路寫到利用物件鍵值唯一性的字典法,並比較各自的取捨。原理都寫在程式碼裡,直接看例子最快。
利用 indexOf 回傳「第一次出現的位置」這個特性,只保留位置等於當前索引的元素:
function onlyUnique(value, index, self) {
return self.indexOf(value) === index;
}
var a = ['a', 1, 'a', 2, '1'];
var unique = a.filter(onlyUnique); // ['a', 1, 2, '1']
先取物件屬性再去重的組合寫法:
var ages = array.map(function (obj) { return obj.age; });
ages = ages.filter(function (v, i) { return ages.indexOf(v) == i; });
console.log(ages); // => [17, 35]
順帶一提,filter 本身就是個好用的工具,例如篩出大於等於 10 的值:
var filtered = [12, 5, 8, 130, 44].filter(function (e) { return e >= 10; });
// [12, 130, 44]
封裝成通用函式(不相容 IE7):
function unique(array) {
return array.filter(function (el, index, arr) {
return index == arr.indexOf(el);
});
}
這種寫法的時間複雜度是 O(n²),因為每個元素都要做一次 indexOf 搜尋,資料量大時會明顯變慢。
利用 Object 的鍵不能重複這個特性,把元素當成 key 塞進物件,天然就完成去重了:
var arr = ["北京", "上海", "天津", "武漢", "上海", "天津", "北京"];
var json = {};
for (var i = 0; i < arr.length; i++) {
json[arr[i]] = arr[i];
}
arr = [];
for (var key in json) {
arr.push(key);
}
console.log(arr.toString()); // "北京,上海,天津,武漢"
Array、JSON 與 {} 三者其實都是 Object,寫哪一種都可以,效果一樣。這個方法速度非常快,但有兩個必須知道的限制:
第一,元素的型別會被改變。物件的鍵一律是字串,所以原本的數字 1 出去之後會變成字串 '1'。
第二,無法區分 1 與 '1',它們會被視為同一個鍵。
先把陣列排序,讓相同的值靠在一起,再用正則把連續重複的段壓掉:
// 去除陣列中重複值(相容 IE7)
function getNoRepeat(s) {
return s.sort().join(",,")
.replace(/(,|^)([^,]+)(,,\2)+(,|$)/g, "$1$2$4")
.replace(/,,+/g, ",")
.replace(/,$/, "")
.split(",");
}
var arr = ["北京", "上海", "天津", "武漢", "上海", "天津", "北京"];
arr = getNoRepeat(arr);
console.log(arr.length); // 4
console.log(arr.toString()); // "北京,上海,天津,武漢"
或者用遞迴從尾端往前比對,相同就砍掉:
var arr = [6, 4, 6, 9, '6', 13, 56, 9, '11', 1, 8, '7', 17, 5, 45, 3, 7];
function unqiue(array) {
// 排序成隊列,讓相同元素相鄰
array.sort(function (m, n) { return m - n; });
// 從隊尾往前比,相同就刪掉
function loop(index) {
if (index >= 1) {
if (array[index] === array[index - 1]) {
array.splice(index, 1);
}
loop(index - 1);
}
}
loop(array.length - 1);
return array;
}
要注意這兩種做法都會破壞原始陣列(排序是原地進行的),若原陣列還要繼續使用,記得先複製一份。
var arr = [1, 3, 4, 56, 3, '1', 7, 9, 7];
var result = [];
function isMatch(array, n) {
for (var i = 0; i < array.length; i++) {
if (array[i] === n) return true;
}
return false;
}
function unqiue(array) {
for (var i = 0; i < array.length; i++) {
if (!isMatch(result, array[i])) {
result.push(array[i]);
}
}
return result;
}
console.log(unqiue(arr)); // [1, 3, 4, 56, '1', 7, 9]
這裡有個細節值得注意:比較運算子一定要用全等 === 而不是 ==。若用雙等號,數字 1 與字串 '1' 會被判定為相同,去重結果就會少一項。這個坑在字典法裡也同樣存在。
indexOf 是 ECMAScript 5 才加入的方法,IE8 及以下不支援,需要自己補一個:
if (!Array.prototype.indexOf) {
Array.prototype.indexOf = function (item) {
var result = -1, a_item = null;
if (this.length == 0) return result;
for (var i = 0, len = this.length; i < len; i++) {
a_item = this[i];
if (a_item === item) {
result = i;
break;
}
}
return result;
};
}
如果目標環境允許使用 ES6,直接用 [...new Set(arr)] 或 Array.from(new Set(arr)) 一行搞定,而且 Set 能正確區分 1 與 '1'、也能存放物件參照,是四種寫法裡語意最乾淨的。若需要相容舊瀏覽器,字典法在效能與簡潔度之間最平衡,只要記住型別會被轉成字串這件事;而若元素是物件,就必須改用「以唯一識別欄位當鍵」或 filter + indexOf 搭配自訂比較函式。