Daily-Interview-Question
Daily-Interview-Question copied to clipboard
Advanced-Frontend
第 59 题：给定两个数组，写一个方法来计算它们的交集。
例如：给定 nums1 = [1, 2, 2, 1]，nums2 = [2, 2]，返回 [2, 2]。
var nums1 = [1, 2, 2, 1], nums2 = [2, 2, 3, 4];
// 1.
// 有个问题， [NaN].indexOf(NaN) === -1
var newArr1 = nums1.filter(function(item) {
return nums2.indexOf(item) > -1;
});
console.log(newArr1);
// 2.
var newArr2 = nums1.filter((item) => {
return nums2.includes(item);
});
console.log(newArr2);
var nums1 = [1, 2, 2, 1], nums2 = [2, 2], result=[];
nums1.forEach(function(val) {
if(nums2.includes(val)) {
result.push(val);
}
})
console.log(result);
function union (arr1, arr2) { return arr1.filter(item => { return arr2.indexOf(item) > - 1; }) } const a = [1, 2, 2, 1]; const b = [2, 3, 2]; console.log(union(a, b)); // [2, 2]
let intersection = (...arg) => arg[0].filter(v => arg[1].includes(v));
解法有点问题，intersection([1,2,2,1],[2,1])
const nums1 = [1, 2, 2, 1];
const nums2 = [2, 2];
const nums = nums1.filter(v => nums2.some(w => w === v))
console.log(nums)
之前的错了，更新一下，感觉可以
const nums1 = [1, 2, 2, 1];
const nums2 = [2, 2];
const doit = (array1, array2) => {
const tmp = [...array2]; // 避免修改array2，使函数doit变得纯洁
return array1.filter(v => {
const index = tmp.indexOf(v);
if(index > -1) {
tmp.splice(index, 1);
return true;
}
return false;
})
}
console.log(doit(nums1, nums2))
返回所有符合结果的交集。
function isExsitWith(numGroup1, numGroup2) {
let betterArray = [];
let eachCode = []
numGroup1.forEach(val=>{
eachCode.push(val);
if(numGroup2.toString().indexOf(eachCode.toString()) == -1) {
eachCode.pop()
eachCode.length > 1 && betterArray.push(eachCode)
eachCode = []
}
})
return betterArray;
}
console.log(
isExsitWith([1, 2, 2, 1, 1, 9, 9, 6, 1, 1, 2, 3, 3], [2, 2, 9, 9, 6,])
)
这道题不是工程题，是道算法题。~~求的是两个数组的最长公共子序列~~ (子序列要求顺序，交集不需要）。所以上面用一个filter一个includes或者indexOf的都是错的。
反例很简单。
var nums1 = [1]
var nums2 = [1,1]
或者
var nums1 = [1,1]
var nums2 = [1]
交集应该是[1]
跑一下你们的方法就能知道错了。
这道题两种思路，空间换时间，或者不用额外空间就提升时间复杂度。
空间换时间的思路是用个Hash表来存数组1的元素以及出现的个数（此处需要遍历n次，并存一个n级别的空间）。
遍历数组2，发现数组2里有Hash表里的值就存到Result数组里，并把Hash表内该值次数减一（为0之后就Delete）。如果不存在Hash表里，就跳过。这样时间复杂度就是(m+n)
不用额外空间，就用遍历n的时候，判断值在不在m里，如果在，把m里的该值push到Result数组里，并将该值从m数组里删掉（用splice）。这样就是不用额外空间，但是提高了时间复杂度。
let nums1 = [1, 2, 2, 1], nums2 = [2, 2, 1, 3]
let result = nums1.filter(item => {
let idx = nums2.indexOf(item)
if (idx !== -1) {
nums2.splice(idx, 1)
return item
}
})
console.log(result) //[1, 2, 2]
let arr0 = [1, 2, 3, '5', '你好啊', 7],
arr1 = [2, 7, 9, 3, 'hello', '你好啊', 120];
const dorseyHandle = (arr0, arr1) => {
let res = [],
map = {},
_arr1;
// 确定哪个数组长度更长
let _arr0 = arr0.length > arr1.length ? ( _arr1 = arr1, arr0 ) : ( _arr1 = arr0 , arr1 ); // 这里是arr0更长
_arr0.map(( item, index ) => {
map[item] = 'undefined' !== typeof map[item] ? map[item] + 1 : 1;
});
_arr1.forEach(item => {
if('undefined' !== typeof map[item]){
res.push(item);
map[item] === 1 ? delete map[item] : map[item] -= 1;
}
});
return res;
}
console.log(dorseyHandle(arr0, arr1));
另一种方式
let arr0 = [1, 2, 3, '5', '你好啊', 7],
arr1 = [2, 7, 9, 3, 'hello', '你好啊', 120];
const dorseyHandle = ( arr0, arr1 ) => {
return arr0.filter( item => {
let index = arr1.indexOf(item);
if(-1 !== index){
arr1.splice(index, 1);
return item;
}
});
}
console.log(dorseyHandle(arr0, arr1));
哈希表，时间复杂度O(m + n) m为nums1长度，n为nums2长度
const intersect = (nums1, nums2) => {
const map = {}
const res = []
for (let n of nums1) {
if (map[n]) {
map[n]++
} else {
map[n] = 1
}
}
for (let n of nums2) {
if (map[n] > 0) {
res.push(n)
map[n]--
}
}
return res
}
let intersection = (...arg) => arg[0].filter(v => arg[1].includes(v));
[1,2,2,1],[2] 情况不成立
这道题不是工程题，是道算法题。求的是两个数组的最长公共子序列。所以上面用一个filter一个includes或者indexOf的都是错的。
反例很简单。
var nums1 = [1] var nums2 = [1,1]或者
var nums1 = [1,1] var nums2 = [1]最长公共子序列应该是[1]
跑一下你们的方法就能知道错了。
我试了 可以啊
const a = [1]
const b = [1, 1]
function fn(arr1, arr2) {
return arr1.filter(item => {
return arr2.includes(item)
})
}
console.log(fn(a, b))//[1]
/* 第 59 题：给定两个数组，写一个方法来计算它们的交集。
例如：给定 nums1 = [1, 2, 2, 1]，nums2 = [2, 2]，返回 [2, 2]。 */
// 思路：遍历数组1，对每个元素判断其是否在数组2中，存在则提出来放到一个新数组里，并且从数组2中剔除，以确保下一次遍历不会出现重复的。 // 由于Array.splice()函数效率比较低，所以采用空间换取时间的方式，剔除的过程是将其他非交集元素放到新数组里。 // 想了想，还是用简单的splice吧。
function intersect (ary1, ary2) {
let longAry, shortAry
// 不取长短数组也行吧。
if (ary1.length > ary2.length) {
longAry = ary1
shortAry = ary2
} else {
longAry = ary2
shortAry = ary1
}
let tmpAry = []
try {
longAry.forEach(el => {
if (shortAry.length === 0) {
throw new Error('short array.lenth === 0')
}
let index = shortAry.indexOf(el)
if (index > -1) {
// 短数组中存在元素的情况
shortAry.splice(index, 1)
tmpAry.push(el)
}
})
} catch (error) {
console.log(error)
}
return tmpAry
}
console.log(intersect([1, 2, 2, 1], [2, 2]))
这道题不是工程题，是道算法题。求的是两个数组的最长公共子序列。所以上面用一个filter一个includes或者indexOf的都是错的。 反例很简单。
var nums1 = [1] var nums2 = [1,1]或者
var nums1 = [1,1] var nums2 = [1]最长公共子序列应该是[1] 跑一下你们的方法就能知道错了。
我试了 可以啊
const a = [1] const b = [1, 1] function fn(arr1, arr2) { return arr1.filter(item => { return arr2.includes(item) }) } console.log(fn(a, b))//[1]
你的a换成[1,1],b换成[1]再试试
这道题不是工程题，是道算法题。求的是两个数组的最长公共子序列。所以上面用一个filter一个includes或者indexOf的都是错的。 反例很简单。
var nums1 = [1] var nums2 = [1,1]或者
var nums1 = [1,1] var nums2 = [1]最长公共子序列应该是[1] 跑一下你们的方法就能知道错了。
我试了 可以啊
const a = [1] const b = [1, 1] function fn(arr1, arr2) { return arr1.filter(item => { return arr2.includes(item) }) } console.log(fn(a, b))//[1]你的a换成[1,1],b换成[1]再试试
是有问题。有受到调用数组长度影响。
不会受到长度影响
let intersection = (...arg) => {
let result = [];
arg[0].forEach((v) => {
if (arg[1].indexOf(v) !== -1) {
result.push(v);
arg[1].splice(arg[1].indexOf(v), 1);
}
}); return result;
}
` /**
@info: 给定 nums1 = [1, 2, 2, 1]，nums2 = [2, 2]，返回 [2, 2]。
*/
var nums1 = [1,1];
var nums2 = [1];
function common(nums1,nums2) {
var resp = [];
nums1.forEach(ele => {
let idx = nums2.indexOf(ele);
if(idx > -1) {
resp.push(ele);
nums2.splice(idx, 1)
}
})
return resp
}
console.log(common(nums1,nums2))`
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
nums1.sort((a, b) => a - b)
nums2.sort((a, b) => a - b)
let arr = []
let i = 0
let j = 0
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
arr.push(nums1[i])
i++
j++
} else if (nums1[i] > nums2[j]) {
j++
} else {
i++
}
}
return arr
}
不会受到长度影响
let intersection = (...arg) => { let result = []; arg[0].forEach((v) => { if (arg[1].indexOf(v) !== -1) { result.push(v); arg[1].splice(arg[1].indexOf(v), 1); } }); return result; }
不错，个人感觉要是能在不改变原数组的基础上实现就更好了☺
你们上面都不对，这个才是正确的。 时间复杂度 O(n)
let insertSection = (...args) => {
let [ first, second ] = args
let res = []
while (first.length) {
let item = first.pop()
let index = second.indexOf (item)
if (index > -1) {
second.splice(index, 1)
res.push(item)
}
}
return res
}
// test
var nums1 = [1]
var nums2 = [1,1]
var res = insertSection(nums1, nums2)
console.log(res) // [1]
var nums1 = [2, 2, 1], nums2 = [1 , 2, 2, 3, 4];
var res2 = insertSection(nums1, nums2)
console.log(res2) // [1, 2, 2]
你们上面都不对，这个才是正确的。 时间复杂度 O(n)
let insertSection = (...args) => { let [ first, second ] = args let res = [] while (first.length) { let item = first.pop() let index = second.indexOf (item) if (index > -1) { second.splice(index, 1) res.push(item) } } return res } // test var nums1 = [1] var nums2 = [1,1] var res = insertSection(nums1, nums2) console.log(res) // [1] var nums1 = [2, 2, 1], nums2 = [1 , 2, 2, 3, 4]; var res2 = insertSection(nums1, nums2) console.log(res2) // [1, 2, 2]
这是O(m,n)复杂度吧
function findTheSameNumber(nums1, nums2) {
const res = [];
for (let i = 0; i < nums1.length; i++) {
if (nums2.length <= 0) {
break;
}
const val = nums1[i];
const index = nums2.indexOf(val);
if (index > -1) {
nums2.splice(index, 1);
res.push(val);
}
}
return res;
}
const nums1 = [1, 2, 2, 1];
const nums2 = [2, 2];
console.log(findTheSameNumber(nums1, nums2));
你们上面都不对，这个才是正确的。 时间复杂度 O(n)
let insertSection = (...args) => { let [ first, second ] = args let res = [] while (first.length) { let item = first.pop() let index = second.indexOf (item) if (index > -1) { second.splice(index, 1) res.push(item) } } return res } // test var nums1 = [1] var nums2 = [1,1] var res = insertSection(nums1, nums2) console.log(res) // [1] var nums1 = [2, 2, 1], nums2 = [1 , 2, 2, 3, 4]; var res2 = insertSection(nums1, nums2) console.log(res2) // [1, 2, 2]
emmm。。你这个也是n方的解法。你先是一层循环，里面用了indexOf和splice，然后indexof和splice都是O(n)
function intersect(m,n){ return new Set(m).size<=new Set(n).size?n.filter(x=>new Set(m).has(x)):m.filter(x=>new Set(n).has(x)) } console.log(intersect([1, 2, 2, 1],[2, 2, 1]))
console.log(intersect([1,1],[1,2]))
function getIntersection(nums1,nums2){
let data1 = nums1.length > nums2.length ? nums1 : nums2
let data2 = nums1.length > nums2.length ? nums2 : nums1
let result = [];
data2.forEach(item => {
if(data1.indexOf(item) !== -1) {
result.push(item)
data1.splice(data1.indexOf(item),1)
}
})
console.log(result)
return result;
}
function intersect(m,n){ return m.length>n.length ?n.filter(x=>new Set(m).has(x)):m.filter(x=>new Set(n).has(x)) } console.log(intersect([1, 2, 2, 1],[2, 2, 1]))
测试用例console.log(intersect([1,1],[1,2])) 输出应该是[1], 但你的是[1,1]
function intersect(m,n){
let sortedM = m.sort((a,b)=>a-b);
let sortedN = n.sort((a,b)=>a-b)
const mLength = m.length;
const nLength = n.length;
const intersection = []
while(sortedM.length&&sortedN.length){
const a = sortedM[0];
const b = sortedN[0];
if(a>b){
sortedN.shift();
}
else if (a<b){
sortedM.shift();
}
else{
intersection.push(sortedM.shift());
sortedN.shift();
}
}
return new Set(intersection);
}
O(min(n,m))
function intersect(m,n){ let sortedM = m.sort((a,b)=>a-b); let sortedN = n.sort((a,b)=>a-b) const mLength = m.length; const nLength = n.length; const intersection = [] while(sortedM.length&&sortedN.length){ const a = sortedM[0]; const b = sortedN[0]; if(a>b){ sortedN.shift(); } else if (a<b){ sortedM.shift(); } else{ intersection.push(sortedM.shift()); sortedN.shift(); } } return new Set(intersection); }
你sort一下就已经是O(n lgn)了。。
O(min(n,m))
function intersect(m,n){ let sortedM = m.sort((a,b)=>a-b); let sortedN = n.sort((a,b)=>a-b) const mLength = m.length; const nLength = n.length; const intersection = [] while(sortedM.length&&sortedN.length){ const a = sortedM[0]; const b = sortedN[0]; if(a>b){ sortedN.shift(); } else if (a<b){ sortedM.shift(); } else{ intersection.push(sortedM.shift()); sortedN.shift(); } } return new Set(intersection); }你sort一下就已经是O(n lgn)了。。
Damn... 已修改
大佬们 我这样对不对
function fn(a, b) {
const result = [];
const map = a.reduce((obj, item) => {
obj[item] ? obj[item]++ : obj[item] = 1;
return obj;
}, {});
b.forEach(item => {
if (map[item] && map[item] > 0) {
result.push(item);
map[item]--
}
})
return result
}
console.log(fn([1, 2, 1], [2, 2, 1])) // [2, 1]
你们上面都不对，这个才是正确的。 时间复杂度 O(n)
let insertSection = (...args) => { let [ first, second ] = args let res = [] while (first.length) { let item = first.pop() let index = second.indexOf (item) if (index > -1) { second.splice(index, 1) res.push(item) } } return res } // test var nums1 = [1] var nums2 = [1,1] var res = insertSection(nums1, nums2) console.log(res) // [1] var nums1 = [2, 2, 1], nums2 = [1 , 2, 2, 3, 4]; var res2 = insertSection(nums1, nums2) console.log(res2) // [1, 2, 2]这是O(m,n)复杂度吧
对的 ，写错了。
let num_1 = [1, 1, 2, 9, 9, 9, 5];
let num_2 = [1, 1, 1, 2, 9, 6];
let result = [];
for (let i of num_1) {
let index = num_2.indexOf(i)
if (index != -1) {
result.push(num_2[index]);
num_2.splice(index, 1);
}
}
console.log(result); // [1, 1, 2, 9] => num_1 与 num_2 共存的元素
console.log(num_2); // [1, 6] => num_1 与 num_2 不共存的元素
function intersect(m,n){ return new Set(m).size<=new Set(n).size?n.filter(x=>new Set(m).has(x)):m.filter(x=>new Set(n).has(x)) } console.log(intersect([1, 2, 2, 1],[2, 2, 1]))
console.log(intersect([1,1],[1,2])) @Molunerfinn 这样应该就对了 嘿嘿
先排序
var ans=[],p1=p2=0;nums1.sort(),nums2.sort()
while(nums1[p1]&&nums2[p2])
if(nums1[p1]>nums2[p2])p2++
else if(nums1[p1]<nums2[p2])p1++
else ans.push(nums1[p1]),p1++,p2++
用Map
var ans=[],src1=new Map(),src2=new Map()
nums1.map(v=>src1.set(v,src1.get(v)+1||1))
nums2.map(v=>src2.set(v,src2.get(v)+1||1))
for (var [key1, val1] of src1)
src2.has(key1)&&ans.push(...Array(Math.min(src2.get(key1),val1)).fill(key1))
function fn(arr1, arr2) {
let shortArr = arr1.length > arr2.length ? arr2 : arr1
let longArr = arr1.length > arr2.length ? arr1 : arr2
let map = new Map()
let r = []
for(let i=0; i<shortArr.length; i++) {
if (map.has(shortArr[i])) {
r.push(shortArr[i])
} else if (longArr.includes(shortArr[i])) {
map.set(shortArr[i], true)
r.push(shortArr[i])
}
}
return r
}
- 求交集的时候，遍历是必不可免的，但我们可以选择遍历短的那个数组。
- 建立map表，减少includes的次数，算是一个小优化。
let arr1 = [1, 2, 2, 1];
let arr2 = [2, 1, 2];
function intersectionArray(arr1, arr2) {
let compareArray = function(minArray, maxArray) {
return minArray.filter((item) => {
let index = maxArray.indexOf(item);
if (maxArray.includes(item)) {
maxArray.splice(index, 1);
}
return index > -1;
})
};
if(arr2.length > arr1.length) {
return compareArray(arr1, arr2);
}
return compareArray(arr2, arr1);
}
intersectionArray(arr1, arr2); // [2, 1, 2]
var arr1 = [1, 2, 2, 1];
var arr2 = [2, 1, 2];
Array.from(new Set(arr1.filter((v,i) => arr2.includes(v))))
var arr_1 = [1, 2, 3, 4, 2, 3, 3, 33, 5];
var arr_2 =[1, 2, 3, 2, 3, 5];
arr_1.sort();
arr_2.sort();
var arr1_max_bool = arr_1.length > arr_2.length ? true : false;
if (!arr1_max_bool) {
var tem_arry = arr_1;
arr_1 = arr_2;
arr_2 = tem_arry;
}
var arr_new = [];
var index_1 = 0
var index_2 = 0;
for (var i = 0; i < arr_1.length; i++) {
if (arr_1[index_1] === arr_2[index_2]) {
console.log(i, index_1);
arr_new.push(arr_1[i]);
index_1++;
index_2++;
} else {
index_1++
}
}
console.log(arr_new);
function intersection(arr1,arr2){
let arr3 = [];
for(let i=0; i < arr1.length; i++){
if(arr2.includes(arr1[i])){
arr3.push(arr1[i]);
arr2.splice(arr2.indexOf(arr1[i]),1)
}
}
return arr3
}
var arr1 = [1,2,2,1], arr2 = [2,2,1];
console.log(intersection(arr1,arr2))
看好多人写的不太对啊？贴上我的代码参考一下（用的递归）
let arr1 = [1,2,2,3];
let arr2 = [2,1,2];
// 创建新数组
let result = [];
// 拷贝新数组待用
let arr1New = arr1.slice();
let arr2New = arr2.slice();
function mixedOfArr(){
let a1 = arr1New[0];//每次取数组第一个
let index = arr2New.indexOf(a1);//获取在第二个数组中的下标
if(index>-1){
// 第二个数组中若存在
result.push(a1);
//删除第二个数组中存在的元素
arr2New.splice(index,1);
}
//删除第一个数组中遍历过的元素
arr1New.splice(0,1);
if(arr1New.length!=0&&arr2New.length!=0){
// 递归
mixedOfArr();
}
}
mixedOfArr(arr1New,arr2New)
console.log(result);
function getIntersection(arr1, arr2){ if(!(Array.isArray(arr1) && Array.isArray(arr2))){ return; } return arr1.filter(function(item){ return arr2.includes(item); }) }
这道题不是工程题，是道算法题。求的是两个数组的最长公共子序列 (子序列要求顺序，交集不需要）。所以上面用一个filter一个includes或者indexOf的都是错的。
反例很简单。
var nums1 = [1] var nums2 = [1,1]或者
var nums1 = [1,1] var nums2 = [1]交集应该是[1]
跑一下你们的方法就能知道错了。
这道题两种思路，空间换时间，或者不用额外空间就提升时间复杂度。
空间换时间的思路是用个
Hash表来存数组1的元素以及出现的个数（此处需要遍历n次，并存一个n级别的空间）。 遍历数组2，发现数组2里有Hash表里的值就存到Result数组里，并把Hash表内该值次数减一（为0之后就Delete）。如果不存在Hash表里，就跳过。这样时间复杂度就是(m+n)不用额外空间，就用遍历n的时候，判断值在不在m里，如果在，把m里的该值push到
Result数组里，并将该值从m数组里删掉（用splice）。这样就是不用额外空间，但是提高了时间复杂度。
感谢大佬说明易错点：（用简短的文字就说清楚了思路 ）
- 空间换时间：
function getIntersection (num1, num2) {
const maps = {};
const result = [];
num1.forEach(num => {
if (maps[num]) {
maps[num] += 1;
} else {
maps[num] = 1;
}
});
num2.forEach(num => {
if (maps[num]) {
result.push(num);
maps[num] -= 1;
}
});
return result;
}
- 不使用额外空间：
function getIntersection (num1, num2) {
return num1.filter(num => {
let index = num2.indexOf(num);
if (index !== -1) {
num2.splice(index, 1);
return true;
}
return false;
});
}
这道题不是工程题，是道算法题。求的是两个数组的最长公共子序列 (子序列要求顺序，交集不需要）。所以上面用一个filter一个includes或者indexOf的都是错的。
反例很简单。
var nums1 = [1] var nums2 = [1,1]或者
var nums1 = [1,1] var nums2 = [1]交集应该是[1]
跑一下你们的方法就能知道错了。
这道题两种思路，空间换时间，或者不用额外空间就提升时间复杂度。
空间换时间的思路是用个
Hash表来存数组1的元素以及出现的个数（此处需要遍历n次，并存一个n级别的空间）。 遍历数组2，发现数组2里有Hash表里的值就存到Result数组里，并把Hash表内该值次数减一（为0之后就Delete）。如果不存在Hash表里，就跳过。这样时间复杂度就是(m+n)不用额外空间，就用遍历n的时候，判断值在不在m里，如果在，把m里的该值push到
Result数组里，并将该值从m数组里删掉（用splice）。这样就是不用额外空间，但是提高了时间复杂度。
向大佬学习
let arr1 = [0, 1, 2, 3, 4, 3],
arr2 = [0, 0, 3, 3, 2];
const res = arr1.reduce((acc, cur, idx, arr) => {
if(arr2.includes(cur)) {
acc.push(cur);
arr2.splice(arr2.indexOf(cur), 1);
}
return acc;
}, []);
console.log(res);
let num1 = [2, 3, 3, 1, 2];
let num2 = [1, 2, 2];
let cp1 = num1.slice();
let cp2 = num2.slice();
cp1.sort((a, b) => a - b);
cp2.sort((a, b) => a - b);
let i = 0,
j = 0;
let ret = [];
while (i < cp1.length && j < cp2.length) {
if (cp1[i] === cp2[j]) {
ret.push(cp1[i]);
i++;
j++;
} else if (cp1[i] > cp2[j]) {
j++;
} else {
i++;
}
}
console.log(ret);
O(nlogn + mlogm + min(n, m)) ; l = max(m, n) => O(l * log(l))
// O(N)，for 循环、一次遍历，效率最好。
function getSameArray(arr1, arr2) {
const obj = {}
const arr = []
for (let i=0; i<arr1.length; i++) {
const val = arr1[i];
if (!obj[val]) {
obj[val] = 1
} else {
obj[val] = ++obj[val]
}
}
for (let i=0; i<arr2.length; i++) {
const val = arr2[i]
if (obj[val] > 0) {
obj[val] = --obj[val]
arr.push(val)
}
}
return arr
}
//判断两个数组的并集、交集和差集 //使用set的特性（元素唯一性以及其filter函数）
var union = (arr1,arr2) => new Set([...arr1,...arr2])
var intersect = (arr1,arr2) => new Set([...new Set(arr1)].filter((x)=> new Set(arr2).has(x)))
var difference = (arr1,arr2) => new Set([...new Set(arr1)].filter((x)=> !new Set(arr2).has(x)))
let num_1 = [1, 1, 2, 9, 9, 9, 5]; let num_2 = [1, 1, 1, 2, 9, 6]; let result = []; for (let i of num_1) { let index = num_2.indexOf(i) if (index != -1) { result.push(num_2[index]); num_2.splice(index, 1); } } console.log(result); // [1, 1, 2, 9] => num_1 与 num_2 共存的元素 console.log(num_2); // [1, 6] => num_1 与 num_2 不共存的元素
你这个应该是最简单的
//判断两个数组的并集、交集和差集 //使用set的特性（元素唯一性以及其filter函数）
var union = (arr1,arr2) => new Set([...arr1,...arr2]) var intersect = (arr1,arr2) => new Set([...new Set(arr1)].filter((x)=> new Set(arr2).has(x))) var difference = (arr1,arr2) => new Set([...new Set(arr1)].filter((x)=> !new Set(arr2).has(x)))
你可能需要补一下并集，交集，差集的知识
let nums1 = [1, 2, 2, 1], nums2 = [2, 2, 1, 3] let result = nums1.filter(item => { let idx = nums2.indexOf(item) if (idx !== -1) { nums2.splice(idx, 1) return item } }) console.log(result) //[1, 2, 2]
@tongtannan
你这不考虑item本身强转的时候为false吗？
function fn(arr1, arr2) { let shortArr = arr1.length > arr2.length ? arr2 : arr1 let longArr = arr1.length > arr2.length ? arr1 : arr2 let map = new Map() let r = [] for(let i=0; i<shortArr.length; i++) { if (map.has(shortArr[i])) { r.push(shortArr[i]) } else if (longArr.includes(shortArr[i])) { map.set(shortArr[i], true) r.push(shortArr[i]) } } return r }
- 求交集的时候，遍历是必不可免的，但我们可以选择遍历短的那个数组。
- 建立map表，减少includes的次数，算是一个小优化。
@PeterGooo
也贴一个吧，看了各位大佬的答案，也贴一个吧，轻拍。
/**
* get intersection without duplications
* ### 不满足本题目的要求 ###
* [1,2,1,2], [2,2] --> [2]
* @param {array} arr1
* @param {array} arr2
* @returns {array}
*/
const getIntersectionSet = (arr1, arr2) => {
let newArr1 = Array.from(new Set(arr1));
let newArr2 = Array.from(new Set(arr2));
return newArr1.filter(item => newArr2.includes(item));
};
/**
* get intersection include duplications
* [1,2,1,2], [2,2] --> [2,2]
* @param {array} arr1
* @param {array} arr2
* @returns {array}
*/
const getIntersection = (arr1, arr2) => {
let result = [];
let tempArr = [...arr2];
for (let item of arr1) {
if (tempArr.length === 0) {
break;
}
let idx = tempArr.indexOf(item);
if ( idx >= 0 ) {
result.push(item);
tempArr.splice(idx, 1);
}
}
return result;
};
` let arr1 = [1, 2, 2, 3]; let arr2 = [2, 2];
let arr3 = [];
arr1.forEach((item) => {
console.log(item);
for (let i = 0; i < arr2.length; i++) {
if (item == arr2[i]) {
arr3.push(item);
arr2.splice(i,1)
return;
}
}
});
console.log(arr3);`
function fn(arr1, arr2) { let shortArr = arr1.length > arr2.length ? arr2 : arr1 let longArr = arr1.length > arr2.length ? arr1 : arr2 let map = new Map() let r = [] for(let i=0; i<shortArr.length; i++) { if (map.has(shortArr[i])) { r.push(shortArr[i]) } else if (longArr.includes(shortArr[i])) { map.set(shortArr[i], true) r.push(shortArr[i]) } } return r }
- 求交集的时候，遍历是必不可免的，但我们可以选择遍历短的那个数组。
- 建立map表，减少includes的次数，算是一个小优化。
这个算法有bug。比如arr1 = [1,2,1,2,1], arr2 = [1,0,0,0,0,0,0,0,0,0,0] 这个算法得到的交集是[1,1,1]，很明显出错了。看来上面那个是不能使用map，以及要将indexOf的元素，splice掉。
function fn(arr1, arr2) {
if (arr1.length > arr2.length) [arr1, arr2] = [arr2, arr1]
let r = []
for(let i=0; i<arr1.length; i++) {
let findIndex = arr2.indexOf(arr1[i])
if (findIndex !== -1) {
r.push(arr1[i])
arr2.splice(findIndex, 1)
}
}
return r
}
const doIntersec = (list1, list2) => {
let short, long;
if (list1.length > list2.length) {
short = [...new Set(list2)];
long = [...new Set(list1)];
} else {
short = [...new Set(list1)];
long = [...new Set(list2)];
}
return short.filter(item => long.includes(item));
};
这个问题描述有问题，如果是求交集，那么应该是两个集合的运算，而集合具有互异性，这样像[1,2,2,1]这样的数组就不能视为集合，自然也不存在所谓的交集。我认为这个题目更好的描述是“求两个数组的最长公共子序列”。
如果是两个集合求交集，那么利用 Set 的 has 方法就很简单了：
const intersection = (a, b) => new Set([...a].filter(x => b.has(x)));
如果是两个数组的最长公共子序列，这位大佬的答案就很完美了。
function getIntersection(a = [], b = []) {
if (a instanceof Array && b instanceof Array) {
return a.map((e, i) => b.includes(e) && b[i] ? e : '').filter(e => e !== '');
} else {
throw 'params error';
}
}
// let nums1 = [1, 2, 2, 1];
// let nums2 = [2, 2];
var nums1 = [1]
var nums2 = [1,1]
log(getIntersection(nums2, nums1));
思路：遍历arr1，看看值在arr2中是否存在，如果在arr2中存在，就把对应的值放到一个新的数组中。
function getCoincide (arr1, arr2) {
var arr = []
var arr22 = arr2
arr1.forEach(item => {
let temp = arr22.indexOf(item)
if(temp !== -1){
arr.push(arr22[temp])
arr22.splice(temp,1)
}
})
return arr
}
var a = [1, 2, 2, 1]
var b = [2, 3]
getCoincide(a,b) // [2]
刚开始以为很简单，啪啪啪写了下面这段丢人的代码：
// 不严谨的写法
function getIntersection(arr1, arr2) {
return arr1.filter(item => arr2.includes(item));
}
看了 @Molunerfinn 的回答后，才知道自己错了，下面是修正后的：
function getIntersection(arr1, arr2) {
let result = [];
[...arr1].forEach((item, index, array) => {
if (arr2.includes(item)) {
result.push(item);
array.splice(index, 1);
}
});
return result;
}
let a = new Set([1, 2, 3]); let b = new Set([4, 3, 2]);
// 并集 let union = new Set([...a, ...b]); // Set {1, 2, 3, 4}
// 交集 let intersect = new Set([...a].filter(x => b.has(x))); // set {2, 3}
// 差集 let difference = new Set([...a].filter(x => !b.has(x))); // Set {1}
const intersection = (arr1, arr2) => {
const _arr2 = [...arr2];
return arr1.filter(v1 => {
const index = _arr2.findIndex(v2 => v2 === v1);
return index >= 0 ? (_arr2.splice(index, 1), true) : false;
});
};
例如：给定 nums1 = [1, 2, 2, 1]，nums2 = [2, 2]，返回 [2, 2]。
var nums1 = [1, 2, 2, 1], nums2 = [2, 2, 3, 4]; // 1. // 有个问题， [NaN].indexOf(NaN) === -1 var newArr1 = nums1.filter(function(item) { return nums2.indexOf(item) > -1; }); console.log(newArr1); // 2. var newArr2 = nums1.filter((item) => { return nums2.includes(item); }); console.log(newArr2);
var nums1 = [1, 2, 2, 1], nums2 = [2, 3, 4]; 这种情况你也是返回 [2,2]
var arr1 = [1, 2, 2, 1]; var arr2 = [2, 1, 2]; Array.from(new Set(arr1.filter((v,i) => arr2.includes(v))))
let a = new Set([1, 2, 3]); let b = new Set([4, 3, 2]);
// 并集 let union = new Set([...a, ...b]); // Set {1, 2, 3, 4}
// 交集 let intersect = new Set([...a].filter(x => b.has(x))); // set {2, 3}
// 差集 let difference = new Set([...a].filter(x => !b.has(x))); // Set {1}
这样默认数组里面不会有重复的, [1,2,2]和[1,2,2,3] 算出来是[1,2] 如果按照集合的思路讲是没问题的 但是如果按照数组求相同的话 感觉还是有问题
const intersection = (nums1: number[], nums2: number[]) => {
const set1 = new Set(nums1)
const set2 = new Set(nums2)
const [minSet, maxSet] = set1.size > set2.size ? [set2, set1] : [set1, set2]
return Array.from(minSet).reduce((result, value) => {
return maxSet.has(value) ? result.concat(value) : result
}, [] as number[])
}
const intersection = (arr1,arr2)=>{ let resultArr = [] arr1.map((item)=>{ if(arr2.indexOf(item)!==-1&&resultArr.indexOf(item)===-1){ resultArr.push(item) } }) return resultArr } let arr1 = [1,2,2,1] let arr2 = [2] console.log(intersection(arr1,arr2))
var nums1 = [1, 2, 2, 1]
var nums2 = [2, 2]
function _intersect (nums1, nums2) {
if (nums1.length < nums2.length) {
return nums1.filter(item => nums2.some(num => num === item))
}
return nums2.filter(item => nums1.some(num => num === item))
}
_intersect(nums1, nums2) // [2, 2]
let a = [1, 2, 2, 1],
b = [2, 1];
let result = [];
if (a.length > b.length) [a, b] = [b, a];
for (let i=0;i<a.length;i++){
let index = b.indexOf(a[i]);
if (index > -1) {
result.push(a[i]);
b[index] = null;
}
}
我觉得这个题目本身就有问题。数组可以有重复的元素，而集合的元素具有唯一性，相当于Set类型，所以对数组的交集、并集、差集感觉都没有意义。这个题目可能表达的意思是‘计算两个数组的相同元素’。
// 例如：给定 nums1 = [1, 2, 2, 1]，nums2 = [2, 2]，返回 [2, 2]。
const compare=(arr1,arr2)=>{
let cache={}
let result=[]
for(let item of arr1){
cache[item]=!cache[item]?1:cache[item]+1
}
for(let item of arr2){
if(cache[item]){
cache[item]--
result.push(item)
}
}
return result
}
const nums1 = [ 1, 2, 2, 1 ]
const nums2 = [2, 3, 4]
function intersection(arr1, arr2) {
const res1= arr1.filter(v=> arr2.includes(v))
const res2= arr2.filter(v=> arr1.includes(v))
return res1.length > res2.length ? res2 : res1
}
console.log(intersection(nums1, nums2));
let intersect = (...args) => ([...new Set(args.flat())].filter(item => args.every(arr => arr.includes(item)))) let res = intersect([1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6], [3, 6, 9]) let res1 = intersect([1,3,5,7], [2,4,6,8]) let res2 = intersect([1,1], [1])
console.log(res) // [3]
console.log(res1) // []
console.log(res2) // [1]
思路：合并、去重 传入的数组生成新数组，然后将新数组的每一项通过 every() 对比 PS: flat() 只是用来偷懒的，而且此方法不够完善，只能对比一维数组
function test(obj1=[],obj2=[]){
const arr=[]
if(obj1.length > obj2.length){
for (let i = 0; i < obj1.length; i++) {
if (obj1[i] == obj1[i + 1]) continue;
for (let j = 0; j < obj2.length; j++) {
if(obj1[i] == obj2[j]){
arr[arr.length] = obj1[i]
}
}
}
}else{
for (let i = 0; i < obj2.length; i++) {
if (obj2[i] == obj2[i + 1]) continue;
for (let j = 0; j < obj1.length; j++) {
if (obj2[i] == obj1[j]) {
arr[arr.length] = obj2[i]
}
}
}
}
return arr;
}
console.log('arr', test([1, 2, 2, 1,3], [2, 2,3]))
小小菜鸟 最原始对的方法 来一个
function func(arr1, arr2) {
let maxArr = arr1.length > arr2.length ? arr1: arr2
let minArr = arr1.length > arr2.length ? arr2: arr1
return maxArr.filter(item => minArr.find(min => min === item))
}
var nums1 = [1, 2, 2, 5, 1]
var nums2 = [2, 2,4, 5]
console.log(func(nums1, nums2))
function fn(a1,a2){
var c = [];
var d = [];
if(a1.length>a2.length){
c = a1;
d = a2
}else{
c = a2;
d = a1;
}
return d.filter(i=>{
return c.indexOf(i)>-1
})
}
fn([1,1,1,12,3,4,7],[1,1,23,5,7]) // [1,1,7]
重新赋值的地方，还有优化的空间。
function intersection(arr1,arr2) {
var usedArr1 = [];
var usedArr2 = [];
var result = [];
for (var i = 0; i < arr2.length; i++) {
var a2 = arr2[i];
for (var j = 0; j < arr1.length; j++) {
var a1 = arr1[j];
if(a2 === a1 && !usedArr1[j] && !usedArr2[i]){
result.push(a2);
usedArr1[j] = true;
usedArr2[i] = true;
}
}
}
return result;
}
var nums1 = [1,2,3] var nums2 = [2,3,4] var result = Array.from(new Set([...nums1,...nums2])) console.log(result)
function union(arr1, arr2) {
const temp = {},
result = []
for (let i = 0; i < arr1.length; i++) {
for (let j = 0; j < arr2.length; j++) {
if (arr1[i] === arr2[j] && !temp[j]) {
result.push(arr1[i])
temp[j] = true
break
}
}
}
return result
}
console.log(union([1, 2, 2, 2, 1], [2, 2, 3, 4]))
空间换时间
Set 的实现一般是红黑树，查找的时间复杂度是O(logN)，而V8的实现是哈希表，时间复杂度是O(1). 在数据量很大时，会比 indexOf 快很多
function sulotion(arr1, arr2) {
const temp = new Set(arr1);
const res = new Set();
arr2.forEach(item => temp.has(item) && res.add(item))
return Array.from(res);
}
var nums1 = [1],nums2 = [1,1];
var result = [];
function sameValue(arr1,arr2){
var demo1 = arr1.length>=arr2.length?arr1:arr2;
var demo2 = arr1.length<arr2.length?arr1:arr2;
demo1.map((value1,index1)=>{
demo2.map((value2,index2)=>{
if(value1 === value2){
result.push(value1)
demo1.splice(index1,1)
demo2.splice(index2,1)
sameValue(demo1,demo2)
}
})
})
return result;
}
sameValue(nums1,nums2)
这道题不是工程题，是道算法题。~求的是两个数组的最长公共子序列~ (子序列要求顺序，交集不需要）。所以上面用一个filter一个includes或者indexOf的都是错的。
反例很简单。
var nums1 = [1] var nums2 = [1,1]或者
var nums1 = [1,1] var nums2 = [1]交集应该是[1]
跑一下你们的方法就能知道错了。
这道题两种思路，空间换时间，或者不用额外空间就提升时间复杂度。
空间换时间的思路是用个
Hash表来存数组1的元素以及出现的个数（此处需要遍历n次，并存一个n级别的空间）。 遍历数组2，发现数组2里有Hash表里的值就存到Result数组里，并把Hash表内该值次数减一（为0之后就Delete）。如果不存在Hash表里，就跳过。这样时间复杂度就是(m+n)不用额外空间，就用遍历n的时候，判断值在不在m里，如果在，把m里的该值push到
Result数组里，并将该值从m数组里删掉（用splice）。这样就是不用额外空间，但是提高了时间复杂度。
看到PicGo都猜到是你了 hhhhhh
var intersect = function(nums1, nums2) { var res = []; //包含之后再清除 for(var i=0;i<nums1.length;i++){ if(nums2.includes(nums1[i])){ res.push(nums1[i]); nums2.splice(nums2.indexOf(nums1[i]), 1); } } return res; };
- 表达一下我思路，采用set进行去除重复的元素
function union(nums1, nums2) {
let result = new Set()
nums1.forEach(element => {
if (nums2.includes(element)) {
result.add(element)
}
});
return [...result]
}
const nums1 = [1, 2, 3, 5];
const nums2 = [2, 4, 3, 6];
console.log(union(nums1, nums2))
let num1=[1,2,2,3,1]; let num2=[2,2,3,4]; console.log(num1.filter(value => { if (num2.find((item) => { return value === item }) !== undefined) { return true; } }));
// ES5
function intersect(arr1, arr2) {
return arr1.filter(function (item) {
return arr2.indexOf(item) !== -1;
})
}
//ES6
function intersect(arr1, arr2) {
return arr1.filter(function (item) {
return new Set(arr2).has(item);
})
}
let a1 = [12,22,11,222,678] let a2 = [1,2,3,4,5,678] a1.filter(item => a2.includes(item))
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersect = function(nums1, nums2) { nums1.sort((a, b) => a - b) nums2.sort((a, b) => a - b) let arr = [] let i = 0 let j = 0 while (i < nums1.length && j < nums2.length) { if (nums1[i] == nums2[j]) { arr.push(nums1[i]) i++ j++ } else if (nums1[i] > nums2[j]) { j++ } else { i++ } } return arr }
为啥我运行不了
let arr1 = [1, 4, 2, 4, 7] let arr2 = [1, 4, 4, 234, 89, 6, 7] let arr = []; for (let i = 0; i < arr1.length; i++) { for (let j = 0; j < arr2.length; j++) { if (arr1[i] == arr2[j]) { arr.push(arr1[i]) arr2.splice(j, 1) } } } console.log(arr)
这道题不是工程题，是道算法题。求的是两个数组的最长公共子序列。所以上面用一个filter一个includes或者indexOf的都是错的。 反例很简单。 var nums1 = [1] var nums2 = [1,1] 或者 var nums1 = [1,1] var nums2 = [1] 最长公共子序列应该是[1] 跑一下你们的方法就能知道错了。
我试了 可以啊 const a = [1] const b = [1, 1]
function fn(arr1, arr2) { return arr1.filter(item => { return arr2.includes(item) }) }
console.log(fn(a, b))//[1]
你的a换成[1,1],b换成[1]再试试
这个可以判断两个数组长度，把数组长度短的放在外层不就行了？
let nums1 = [1, 2, 2, 1],
nums2 = [2, 2];
let common = nums1.filter(item => nums2.includes(item))
console.log(common)
let a = new Set([1, 2, 3])
let b = new Set([2, 3, 4])
const intersectByEs6 = new Set([...a].filter(x => b.has(x))) // 2, 3
const intersectByEs5 = [...a].filter(n => [...b].includes(n)) // 2, 3
function handleArr(arrOne,arrTwo){
let newArr = [];
for(let i = 0;i<arrOne.length;i++){
for(let j=0;j<arrTwo.length;j++){
if(arrOne[i]===arrTwo[j]){
newArr.push(arrTwo[j]);
arrTwo.splice(j,1);
break;
}
}
}
return newArr;
}
集合和数组的不同之处在于数组元素可以重复，因此，不可以用集合的方式来解决此题。 我的代码如下：
let num1=[1,2,2,1];
let num2=[2,2];
function unionArr(arr,arr2){
// 长数组为arr
[arr,arr2]=arr.length>arr2.length?[arr,arr2]:[arr2,arr];
return arr.filter(v=>{
let i=arr2.indexOf(v);
//如果存在arr2里面，就先删掉2内匹配的那个元素，返回值为true，否则false
return i>-1?(arr2.splice(i,1),true):false
})
}
思路：对较长数组进行遍历，如果另一数组有对应值，就删掉那个值，把较长数组的那个值保存起来。
补充测试数据:
let arr=[1,2,3,4,6,4,2,8,3,2,1,4,7];
let arr2=[2,5,9,12,1,2,5,3,4,2,1,6,8,5,3];
unionArr(arr,arr2)
//结果 [2, 1, 2, 3, 4, 2, 1, 6, 8, 3]，升序排列为[1, 1, 2, 2, 2, 3, 3, 4, 6, 8].不过有个弊端，arr2由于删除了元素，所以会改变原数组的值，这里给一个改进版，直接修改arr2的拷贝版
function unionArr(arr,arr2){
// 长数组为arr
[arr,arr2]=arr.length>arr2.length?[arr,arr2]:[arr2,arr];
let copyArr=[...arr2];
return arr.filter(v=>{
let i=copyArr.indexOf(v);
//如果存在arr2里面，就先删掉2内匹配的那个元素，返回值为true，否则false
return i>-1?(copyArr.splice(i,1),true):false
})
}
哈希表，时间复杂度O(m + n) m为nums1长度，n为nums2长度
const intersect = (nums1, nums2) => { const map = {} const res = [] for (let n of nums1) { if (map[n]) { map[n]++ } else { map[n] = 1 } } for (let n of nums2) { if (map[n] > 0) { res.push(n) map[n]-- } } return res }
不对啊 const arr1 = [1]; const arr2 = [1,1]; 得到的结果是空的.
function f2(arr1, arr2) {
const arr = [];
for(let index in arr1){
for(let index2 in arr2){
if(arr1[index] === arr2[index2]){
arr.push(arr1[index]);
arr1[index] = NaN;
arr2[index+1] = NaN;
}
}
}
return arr;
}
虽然我只想出这个笨办法
let a = new Set([1, 2, 3]);
let b = new Set([4, 3, 2]);
let intersect = Array.from(new Set([...a].filter(x => b.has(x))));
const intersection = (arr1, arr2) => {
const obj = {}
arr1.forEach(item => obj[item] = 1)
arr2.forEach(item => {
if (obj[item] === 1) {
obj[item] = 2
}
})
return Object.keys(obj)
}
除了要考虑重复项，循环次数最好也尽量少~
const nums1 = [1, 2, 2, 1]
const nums2 = [2, 2]
let nums = []
for (let i of nums1.length <= nums2.length ? nums1 : nums2) {
for (let j of nums1.length <= nums2.length ? nums2 : nums1) {
if (i === j) {
nums.push(i)
break
}
}
}
console.log(nums)
