Javascript系列——對象元素的數組去重實現

概要

這是一篇記錄文，記錄數組操作對象去重的實現。

需求

有這樣一個數組

[{_id: 123,name: '張三'
},{_id: 124,name: '李四'
},{_id: 123,name: '張三'
}]

實際上我們只需要

[{_id: 123,name: '張三'
},{_id: 124,name: '李四'
}]

去重

簡單數組的去重

Array.from(new Set([1,1,2,3,4,4])) // [1,2,3,4]

以對象為元素的數組去重

和數組相關的算法多種多樣，在你以為自己已經掌握數組之后，會發現很多和數組相關的算法仍舊很復雜。

下面我將講述一個入門等級的數組算法，解決上面提出的需求。

1、定義一個函數removeRepeat，它需要傳入2個參數，arr表示需要去重的數組，field表示需要比較的key。比如我們的需求是比較 _id 是否有重復。

function removeRepeat(arr, field){return arr
}

2、需要一個空數組，用來存儲每個對象元素中field對應的value。

let s = []
for(let v of arr){s.push(v[field])
}
//s = [123, 124, 123]

3、將所有field的值存到數組之后，它們的下標一一對應原數組的下標（這點很重要），接著我們需要2個對象集合，result用來存儲s里遍歷出來的元素，如果有重復，就將重復的元素丟到reSet對象里面。

let result = {}, reSet = {}
for(let i=0,len=s.length;i<len;i++){if(!result[s[i]] && result[s[i]] !== 0) {//如果result不存在當前的key并且它不為0時result[s[i]] = i} else {reSet[s[i]] = i}
}
// result = {123: 0, 124: 1} 這是去重重復后的元素
// reSet = {123: 2} 我們將重復的元素123作為key，它的下標2作為value。

4、上一步得到了result和reSet2個對象，那么，我們該用哪個對象來處理原數組的去重呢？只需要reSet，reSet記錄了要去重的對象所在的下標，那么可以直接用splice干掉它。

for(let key in reSet){arr.splice(reSet[key], 1)
}
/* 
arr = [{_id: 123,name: '張三'
},{_id: 124,name: '李四'
}]
*/

5、說明

關鍵的第3和4步，都是用對象來處理，這樣做的好處是時間復雜度可以達到O(1)，如果用數組來保存，則需要2個for循環，時間復雜度變成了O(n2)。

完整源碼

function removeRepeat(arr, field){let s = [], result = {}, reSet = {}for(let v of arr){s.push(v[field])}for(let i=0,len=s.length;i<len;i++){if(!result[s[i]] && result[s[i]] !== 0) {result[s[i]] = i} else {reSet[s[i]] = i}}for(let key in reSet){arr.splice(reSet[key], 1)}return arr
}// removeRepeat(arr, '_id')

補充

受到各路大神的解法影響，我也針對上面代碼的不足做了修改。

1、更簡潔的代碼。

2、支持多個重復對象的去重，缺點是會改變原來的排序。

const removeRepeat = (arr, field) => {let s = {}for(let i=0,len=arr.length;i<len;i++){s[arr[i][field]] = arr[i]}return Object.values(s)
}

總結

數組還有各種有趣的操作，也經常作為各大公司考察的題型之重，多練習和數組相關的算法會很有幫助。

原文地址：https://segmentfault.com/a/1190000012873968