var arr1 = [1,2,3,4,5,6,7] var arr2 = [3,5,7,9,12,14]
求兩個數組的去除重複元素後(指將兩邊的重複元素都刪除,例如3重複,則在結果中不能有3,與數組去重不同)的合併的數組,即數組的並集減交集的部分,不知道這個部分有什麼數學名稱沒有。求一個時間複雜度較低的演算法?
用 set 做索引再遍歷較短的 O(n)
var s1 = new Set(arr1) var s2 = new Set(arr2) if (s1.size > s2.size) { [s1, s2] = [s2, s1] } // 让 s1 较短 s1.forEach(n => s2.has(n) && (s1.delete(n), s2.delete(n))) var result = [...s1, ...s2]
求兩個集合不重合的部分,可以先求兩個集合的並集,然後再去掉公共的元素。 A∪B - A∩B = { x | (x∈A & x∉B) || (x∉A & x∈B) }
用程式的想法來實現是:對兩個數字組合並,然後使用filter方法過濾掉數組a和b中的交集元素。將a.concat(b)中在a不在b中和在b不在a中的元素過濾出來。主要會涉及到數組中是否含有某個元素的判斷,有Array.prototype.indexOf,Set的has方法,Array.prototype.includes三種實作方式。
利用ES5的indexOf方法在不考慮NaN情況下的實作方法:
function difference(a,b) { return a.concat(b).filter(function(v) { return a.indexOf(v) === -1 || b.indexOf(v) === -1 }) }
利用ES6新增的Set集合方法,結合filter方法對合併的陣列進行過濾。
function difference(a, b) { let aSet = new Set(a) let bSet = new Set(b) return a.concat(b).filter(v => !aSet.has(v) || !bSet.has(v)) }
利用ES7新增的Array.prototype.includes陣列方法,用於傳回一個陣列是否包含指定元素,結合filter方法對合併的陣列進行過濾。
function difference(a, b) { return a.concat(b).filter(v => !a.includes(v) || !b.includes(v)) }
這個結果叫做symmetric difference, 在set或multiset上都有定義
複雜度..一般就O(n)了
O(n)
var arr1 = [1,2,3,4,5,6,7]; var arr2 = [3,5,7,9,12,14]; const s = new Set(); let arr = arr1.concat(arr2); arr.forEach(x => s.add(x)); console.log(s);
----------看錯問題了,答案有誤,上面的只是去重了,看下面-------------
----------基礎的for循環遍歷一下就能搞定---------------
var arr1 = [1,2,3,4,5,6,7]; var arr2 = [3,5,7,9,12,14]; var arr = []; for(let i=0; i < arr1.length; i++){ if (!arr2.includes(arr1[i])) { arr.push(arr1[i]); } } for(let i=0; i < arr2.length; i++){ if (!arr1.includes(arr2[i])) { arr.push(arr2[i]); } } console.log(arr);
第一種方法,for
for(let i=0,len=arr2.length;i++){ if(arr1.indexOf(arr2[i])===-1){ arr1.push(arr2[i]); } }
第二種,concat和filter,原理就是合併再去重
var arr=arr1.concat(arr2); arr=arr.filter(function(item,index,self){ return self.indexOf(item) == index; });
var arr2key = (arr, o = {}) => { return arr.reduce((acc, cur) => { acc[cur] = '√'; return acc; }, o); } var mergeAsObj = A => B => { return arr2key(B, arr2key(A)); } var obj2arr = Object.keys; // 组装 var arrMerge = A => B => { return obj2arr( mergeAsObj(A)(B) ) }
用 set 做索引再遍歷較短的 O(n)
求兩個集合不重合的部分,可以先求兩個集合的並集,然後再去掉公共的元素。
A∪B - A∩B = { x | (x∈A & x∉B) || (x∉A & x∈B) }
用程式的想法來實現是:
對兩個數字組合並,然後使用filter方法過濾掉數組a和b中的交集元素。將a.concat(b)中在a不在b中和在b不在a中的元素過濾出來。主要會涉及到數組中是否含有某個元素的判斷,有Array.prototype.indexOf,Set的has方法,Array.prototype.includes三種實作方式。
利用ES5的indexOf方法在不考慮NaN情況下的實作方法:
利用ES6新增的Set集合方法,結合filter方法對合併的陣列進行過濾。
利用ES7新增的Array.prototype.includes陣列方法,用於傳回一個陣列是否包含指定元素,結合filter方法對合併的陣列進行過濾。
這個結果叫做symmetric difference, 在set或multiset上都有定義
複雜度..一般就
O(n)
了----------看錯問題了,答案有誤,上面的只是去重了,看下面-------------
----------基礎的for循環遍歷一下就能搞定---------------
第一種方法,for
第二種,concat和filter,原理就是合併再去重
利用物件的性質來實現
ScreenShot