面試跑一圈下來,最大的收穫是認清自己的差距在哪、知識面有多窄——適度被打擊一下自信心其實有必要的。回頭把「陣列去重」這個看似簡單的題目做一次完整整理。
由簡到繁比较容易理解。先假設要處理的是簡單型別的陣列:
var arr = [1, 2, 2, 3, '5', 6, 5, '', ' ']
裡面只包含數字與字串兩種型別。
最直覺的想法:把陣列複製一份,用兩層迴圈逐一比對目前值與後面所有的值,若與後面所有值都不相等,就把該值放進新陣列。
// 第一種方法
Array.prototype.distinct = function () {
var clone, newArr = [], n = 0;
if (this.length < 2) return;
clone = this;
for (var i = 0, len = this.length; i < len; i++) {
for (var j = i + 1, len2 = clone.length; j < len2; j++) {
if (this[i] !== clone[j]) {
n++;
}
}
if (n == (len - i - 1)) {
newArr.push(this[i])
}
n = 0;
}
return newArr;
}
console.log([1, 2, 2, 3, '5', 6, 5, '', ' '].distinct());
基本能滿足需求,對簡單型別來說不用動太多腦筋。但問題在效能:陣列長度為 n 時,時間複雜度是 O(n²)。陣列一長就很難看。
// 第二種方法
Array.prototype.distinct = function () {
var newArr = this.concat().sort(), self = this;
newArr.sort(function (a, b) {
var n;
if (a === b) {
n = self.indexOf(a);
self.splice(n, 1);
}
});
return self;
}
console.log([1, 2, 2, 3, '5', 6, 5, 6, 6, 15, 5, '5', 5, '', ' '].distinct());
程式碼看起來短了很多,連一個 for 迴圈都沒有。但別被表象騙了——sort 本身的複雜度就不低,而迴圈內又呼叫了 indexOf(O(n))與 splice(O(n)),整體反而可能更慢。而且這個實作會直接修改原陣列,是個副作用陷阱。
// 第三種方法
Array.prototype.distinct = function () {
var newArr = [], obj = {};
for (var i = 0, len = this.length; i < len; i++) {
if (!obj[this[i]]) {
newArr.push(this[i]);
obj[this[i]] = 'new';
}
}
return newArr;
}
console.log([1, 2, 2, 3, '5', 6, 5, 6, 6, 15, 5, '5', 5, '', ' '].distinct());
這個版本的時間複雜度降為 O(n),速度快得多。但執行結果與前面的方法不一致——仔細看會發現它把數字 5 和字串 '5' 當成重複值去掉了。原因是物件屬性名會被強制轉型為字串,兩者在鍵值空間裡撞在一起。
解法是把型別資訊一起編進鍵值:
// 第三種方法補充版
Array.prototype.distinct = function () {
var newArr = [], obj = {};
for (var i = 0, len = this.length; i < len; i++) {
if (!obj[typeof (this[i]) + this[i]]) {
newArr.push(this[i]);
obj[typeof (this[i]) + this[i]] = 'new';
}
}
return newArr;
}
拿更複雜的資料來測試:
console.log([1, null, 2, {a:'vc'}, {}, '5', 6, 5, 6, {a:'vv'}, 15, 5, '5', 5, '', ' ', [1], [1], [1,2], ,].distinct());
問題來了:{a:'vc'}、{}、{a:'vv'} 這三個明顯不同的物件,全被當成同一個值剔除掉了。因為它們轉成鍵值後都是 [object Object]。要正確處理,就得進一步遞迴比對物件的屬性與值:
// 第三種方法加強版
Array.prototype.distinct = function () {
var sameObj = function (a, b) {
var tag = true;
if (!a || !b) return false;
for (var x in a) {
if (!b[x]) return false;
if (typeof (a[x]) === 'object') {
tag = sameObj(a[x], b[x]);
} else {
if (a[x] !== b[x]) return false;
}
}
return tag;
}
var newArr = [], obj = {};
for (var i = 0, len = this.length; i < len; i++) {
if (!sameObj(obj[typeof (this[i]) + this[i]], this[i])) {
newArr.push(this[i]);
obj[typeof (this[i]) + this[i]] = this[i];
}
}
return newArr;
}
用前面的例子測試,基本沒有問題了。這個 sameObj 的實作還有改進空間——例如用 if (!b[x]) 判斷會把值為 0、''、false 的屬性誤判為不存在,嚴謹的寫法應該是 if (!(x in b));另外它也沒有處理陣列與物件的型別區分。
今天的JavaScript有更好的答案。Set 天生就是不重複的集合,一行就能完成基本型別的去重:
var arr = [1, 2, 2, 3, '5', 6, 5, '', ' ']; var unique = [...new Set(arr)]; // Set 使用 SameValueZero 比較,能正確區分 5 與 '5' var unique2 = Array.from(new Set(arr)); // 效果相同
若需要處理物件並保留首次出現的順序,可以用 filter 搭配 indexOf,或用 Map 以物件本身作為鍵(Map 的鍵不轉型,物件之間以參照比較):
var seen = new Set();
var result = arr.filter(function (item) {
var key = JSON.stringify(item); // 依需求決定要用參照還是結構做鍵
if (seen.has(key)) return false;
seen.add(key);
return true;
});
關鍵是:去重前先想清楚「怎樣算重複」。是型別也要比?物件要比結構還是比參照?NaN 要不要視為等於自己?把這個定義想清楚,再選對應的資料結構,就不會像上面那樣一路補丁補到底了。