84669 人が学習中
152542 人が学習中
20005 人が学習中
5487 人が学習中
7821 人が学習中
359900 人が学習中
3350 人が学習中
180660 人が学習中
48569 人が学習中
18603 人が学習中
40936 人が学習中
1549 人が学習中
1183 人が学習中
32909 人が学習中
重複要素を削除した後、2 つの配列のマージされた配列を検索します (両側の重複要素を削除することを指します。たとえば、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