第 59 题：给定两个数组，写一个方法来计算它们的交集。 #102

zeroone001 · 2019-04-21T23:44:31Z

例如：给定 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);

ramey502 · 2019-04-22T00:18:19Z

let intersection = (...arg) => arg[0].filter(v => arg[1].includes(v));

sgzhm4444 · 2019-04-22T00:56:29Z

var nums1 = [1, 2, 2, 1], nums2 = [2, 2], result=[];
nums1.forEach(function(val) {
	if(nums2.includes(val)) {
		result.push(val);
	}
})
console.log(result);

jefferyE · 2019-04-22T00:57:20Z

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]

A0150315 · 2019-04-22T01:14:45Z

let intersection = (...arg) => arg[0].filter(v => arg[1].includes(v));

解法有点问题，intersection([1,2,2,1],[2,1])

yyyddc · 2019-04-22T01:16:37Z

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))

Jon-Millent · 2019-04-22T01:17:20Z

返回所有符合结果的交集。

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,])
)

Molunerfinn · 2019-04-22T01:22:36Z

这道题不是工程题，是道算法题。~~求的是两个数组的最长公共子序列~~ (子序列要求顺序，交集不需要）。所以上面用一个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）。这样就是不用额外空间，但是提高了时间复杂度。

tongtannan · 2019-04-22T01:28:57Z

    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]

dorseysen · 2019-04-22T01:30:33Z

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));

ZodiacSyndicate · 2019-04-22T01:31:54Z

哈希表，时间复杂度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
}

flynngao · 2019-04-22T01:32:57Z

let intersection = (...arg) => arg[0].filter(v => arg[1].includes(v));

[1,2,2,1],[2] 情况不成立

yeyi361936738 · 2019-04-22T01:41:17Z

这道题不是工程题，是道算法题。求的是两个数组的最长公共子序列。所以上面用一个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]

YouziXR · 2019-04-22T01:42:09Z

/* 第 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]))

Molunerfinn · 2019-04-22T01:42:20Z

这道题不是工程题，是道算法题。求的是两个数组的最长公共子序列。所以上面用一个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]再试试

yeyi361936738 · 2019-04-22T01:47:41Z

这道题不是工程题，是道算法题。求的是两个数组的最长公共子序列。所以上面用一个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]再试试

是有问题。有受到调用数组长度影响。

flynngao · 2019-04-22T01:48:31Z

不会受到长度影响

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;
}

GuoYuFu123 · 2019-04-22T01:57:39Z

` /**
@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))`

sogud · 2019-04-22T02:02:08Z

/**
 * @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
}

jichenchen91 · 2019-04-22T02:04:29Z

不会受到长度影响

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;
}

不错，个人感觉要是能在不改变原数组的基础上实现就更好了☺

lzbSun · 2019-04-22T02:08:02Z

你们上面都不对，这个才是正确的。
时间复杂度 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]

thisisandy · 2019-04-22T02:11:48Z

你们上面都不对，这个才是正确的。
时间复杂度 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)复杂度吧

lpeihan · 2019-04-22T02:12:44Z

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));

ZodiacSyndicate · 2019-04-22T02:14:11Z

你们上面都不对，这个才是正确的。
时间复杂度 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)

WEBpeng5202 · 2019-04-22T02:17:00Z

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]))

Rashomon511 · 2019-04-22T02:22:14Z

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;
}

Molunerfinn · 2019-04-22T02:27:34Z

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]

thisisandy · 2019-04-22T02:35:17Z

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);
}

ZodiacSyndicate · 2019-04-22T02:35:56Z

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)了。。

thisisandy · 2019-04-22T02:39:47Z

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... 已修改

zwmmm · 2019-04-22T02:47:20Z

大佬们我这样对不对

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]

zhuyuzhu · 2021-05-16T05:05:01Z

        var arr1 = [1,2,2,1]
        var arr2 = [2,2]
        var map = {}

        arr1.forEach(item => map[item] ? map[item]++ : map[item] = 1)
        var result = arr2.filter(item => {
            if(map[item]){//非undefined，非0
                map[item] --;
                return true
            }
        })

        console.log(result)// [2, 2]

xld1393679430 · 2021-05-18T02:32:23Z

let temp = [...num2]
let array = num1.filter((aItem) => {
    return temp.some((bItem, bIndex) => {
        if (bItem === aItem) {
            temp.splice(bIndex, 1)
            return true
        } else {
            return false
        }
    }) 
})

// const num1 = [1, 2, 2, 1]
// const num2 = [2, 2]

// var num1 = [1]
// var num2 = [1,1]

// var num1 = [1,1]
// var num2 = [1]

// var num1 = [61,24,20,58,95,53,17,32,45,85,70,20,83,62,35,89,5,95,12,86,58,77,30,64,46,13,5,92,67,40,20,38,31,18,89,85,7,30,67,34,62,35,47,98,3,41,53,26,66,40,54,44,57,46,70,60,4,63,82,42,65,59,17,98,29,72,1,96,82,66,98,6,92,31,43,81,88,60,10,55,66,82,0,79,11,81]
// var num2 = [5,25,4,39,57,49,93,79,7,8,49,89,2,7,73,88,45,15,34,92,84,38,85,34,16,6,99,0,2,36,68,52,73,50,77,44,61,48]

测试用例通过

p992202933 · 2021-06-17T07:50:51Z

function isEX(arr_1,arr_2) {
    let list = []
    let clone_arr = []
    for(var i = 0; i < arr_1.length; i++){
        clone_arr = arr_2
        if(clone_arr.length > 0){
            for(var j = 0; j < clone_arr.length; j++) {
                if(arr_1[i] === clone_arr[j]) {
                    list.push(arr_1[i])
                    arr_2.splice(j,1)
                    break
                }
            }            
        }
        else break
    }
    return list
}

hhh 脑子里第一时间想到了这个

yuzhuo25 · 2021-06-24T09:59:57Z

function getRes(a,b) {
let res = []
for(let i = 0; i < a.length; i++) {
b.indexOf(a[i]) > -1 && res.push(a[i]) && b.splice(b.indexOf(a[i]), 1);
}
return res;
}

wangShengCool · 2021-07-07T06:08:24Z

const intersection = (aArray, bArray) => {
const bArraySet = new Set(bArray);
const resultArray = aArray.filter(item => bArraySet.has(item));
return Array.from(resultArray);
}

anguof · 2021-07-12T03:37:34Z

function commonArray(m, n) {
if (m.length <= n.length) {
return m.filter((v) => n.indexOf(v) !== -1);
} else {
return n.filter((v) => m.indexOf(v) !== -1);
}
}

gabengcuiyeye · 2021-08-05T13:39:18Z

function test(a1, a2) {
    let min = a1.length > a2.length ? a2 : a1;
    let max = a1.length > a2.length ? a1 : a2;
    return min.filter(i => max.includes(i))
}

Magiskloop · 2021-08-14T05:08:47Z

可以用Set
数组求交集:
let result = [...new Set(arr)].filter( item => new Set(arr2).has(item));
数组求并集:
let union = [...new Set([...arr,...arr2])]
数组求差集:
let diff = [...new Set(arr)].filter( item => !(new Set(arr2).has(item)));

tchen-l · 2021-09-12T01:19:07Z

let nums2 = [1,1];
const nums2String = nums2.toString()

let result = []
let lastArr = []

for (let i=0;i<nums1.length;i++) {
  lastArr = []
  for (let j=i;j<nums1.length;j++) {
    const num = nums1[j]
    lastArr.push(num)
    if (!nums2String.includes(lastArr.toString()) || lastArr.length <= result.length) {
      break
    }
    result = [...lastArr]
  }
}


console.log(result)

xiangfei1 · 2021-10-14T02:58:39Z

let arr = [1,2,2,1],arr2 = [1,2];
function interSection(arr1,arr2) {
     let result = [];
     let a = arr1.length > arr2.length?arr1:arr2;    //长数组
     let b = arr1.length < arr2.length?arr1:arr2;    //短数组
     let len = arr1.length < arr2.length?arr1.length:arr2.length;    //短数组的长度
     for(let i=0;i<len;i++) {
          let index = a.indexOf(b[i]);
          if(index !== -1) {
              result.push(a[index])   //将交集添加到结果数组
              a.splice(index,1)   //从长数组中剔除找到的元素
           }
     }
     return result;
 }
console.log(interSection(arr,arr2));   //[1,2]
console.log(interSection([1,1],[1]));   //[1]

mygod48 · 2021-10-27T02:55:04Z

传入两个数组，支持引用类型和NaN，使用map
利用引用计数，复杂度O(n)？

const calcArrayIntersection = (arr1,arr2)=>{
    const intersectionMap = new Map();
    const intersectionArr = [];

    arr1.forEach((item)=>{
        const count = intersectionMap.get(item);
        if (!count) {
            intersectionMap.set(item, 1);
        } else {
            intersectionMap.set(item, count + 1);
        }
    }
    );

    arr2.forEach((item)=>{
        const count = intersectionMap.get(item);
        if (count) {
            intersectionArr.push(item);
            intersectionMap.set(item, count - 1);
        }
    }
    );

    return intersectionArr;
}

console.log(calcArrayIntersection([1, 1], [1]));
console.log(calcArrayIntersection([1], [1, 1]));
console.log(calcArrayIntersection([1, 2, 2, 1], [2, 2]));
console.log(calcArrayIntersection([61, 24, 20, 58, 95, 53, 17, 32, 45, 85, 70, 20, 83, 62, 35, 89, 5, 95, 12, 86, 58, 77, 30, 64, 46, 13, 5, 92, 67, 40, 20, 38, 31, 18, 89, 85, 7, 30, 67, 34, 62, 35, 47, 98, 3, 41, 53, 26, 66, 40, 54, 44, 57, 46, 70, 60, 4, 63, 82, 42, 65, 59, 17, 98, 29, 72, 1, 96, 82, 66, 98, 6, 92, 31, 43, 81, 88, 60, 10, 55, 66, 82, 0, 79, 11, 81], [5, 25, 4, 39, 57, 49, 93, 79, 7, 8, 49, 89, 2, 7, 73, 88, 45, 15, 34, 92, 84, 38, 85, 34, 16, 6, 99, 0, 2, 36, 68, 52, 73, 50, 77, 44, 61, 48]));

yaoocheng · 2021-11-12T09:33:16Z

不会算法的我流下了泪水。交集就是你有我也有没错昂。

let arr1 = [1,1,2,3,2], arr2= [2,2,3,4];
let arr = [];
arr1.forEach((item,i) => {
    if(arr2.indexOf(item) > -1) {
        arr = arr.concat(arr2.splice(arr2.indexOf(item),1))
    }
})
console.log(arr)

AAA611 · 2021-11-25T03:48:08Z

下面都是代码，格式不太会搞。。。

时间复杂度为On(n是较短数组的长度)

function fn(arr1, arr2) {
if (!arr1 && !arr2) return
if (!(arr1 instanceof Array) || !(arr2 instanceof Array)) return

  let data1, data2
  arr1.length < arr2.length ? (data1 = arr1, data2 = arr2) : (data1 = arr2, data2 = arr1)

  let i, index
  for (i = 0; i < data1.length; i++) {
    index = data2.indexOf(data1[i])
    if (index == -1) {
      data1.splice(index, 1)
      i--
    } else {
      data2.splice(index, 1)
    }
  }

  return data1
}

fenglizhu · 2021-12-22T04:25:18Z

根据上面 Molunerfinn 的回答，给我很有用的帮助，学到了！！！

解法1：不会出错

let arr1 = [1, 1, 8, 9, 14, 78, 6, '5'];
let arr2 = [1, 1, 8, 5, 6, 48, 21];

let result = [];
for (let i = 0; i < arr1.length; i++) {
  for (let j = 0; j < arr2.length; j++) {
    if(arr1[i] === arr2[j]) {
      if (!result.includes(arr1[i])) {
        result.push(arr1[i])
      }
    };
  }
}
console.log(result);  // [1, 8, 6]

解法2：有缺陷，纯数字和字符串类型数字无法区分

let result1 = []
let obj = {};
for (let i = 0; i < arr1.length; i++) {
  obj[arr1[i]] = arr1[i]
}
for (let j = 0; j < arr2.length; j++) {
  if(obj[arr2[j]] && !result1.includes(arr2[j])) {
    result1.push(arr2[j])
  };
}
console.log(result1); // [1, 8, 5, 6]

sexnmaa · 2022-03-20T04:30:57Z

function same(arr1, arr2) {
  let set = new Set()
  let res = []
  for (let i = 0; i < arr1.length; i++) {
    set.add(arr1[i])
  }
  for (let j = 0; j < arr2.length; j++) {
    if (set.has(arr2[j])) {
      res.push(arr2[j])
    }
  }
  return res
}

johnsoncheg · 2022-04-26T15:54:50Z

function intersection(arr1, arr2) {
	if (!arr2.length || !arr1.length) return []
	const arr = []

	const len1 = arr1.length
	const len2 = arr2.length

	let i = 0, j = 0

	while (i < len1 && j < len2) {
		if (arr1[i] === arr2[j]) {
			arr.push(arr1[i])
			i++
			j++
		} else {
			if (arr1[i+1] === arr2[j] && i !== len1 - 1 && arr1[i+1] !== undefined) {
				i++
			} else if (arr1[i] === arr2[j+1] && j !== len2 - 1 && arr[j+1] !== undefined) {
				j++
			} else {
				if (i < len1) {
					i++
				} else if (j < len2) {
					j++
				}
			}
		}
	}

	return arr
}

const result = intersection([1, 2, 2, 1], [2, 2])

console.log('result', result)

anissa18352869671 · 2022-06-24T15:42:17Z

根据Molunerfinn 大神给的思路
1、空间换时间，map存nums1的每项及每项对应的次数；nums2中有的话，就push到return的数组之中，然后删掉一项map
space = (nums1, nums2) => {
let map = {},
result = [];
nums1.forEach(element => {
if (map[element]) {
map[element]++
} else {
map[element] = 1
}
});
nums2.forEach((element, index) => {
if (map[element]) {
result.push(element);
map[element]--;
}
});
return result;
}
2、不用额外空间
test = (nums1, nums2) => {
let result = [];
for (let i = 0; i < nums1.length; i++) {
if (nums2.indexOf(nums1[i]) > -1) {
console.log(nums1[i])
result.push(nums1[i]);
nums2.splice(nums2.indexOf(nums1[i]), 1)
}
}
return result
}

tanjunfeng · 2023-01-03T07:01:47Z

const nums1 = [1, 2, 2, 1, 3, 5, 'as', '娱乐']
const nums2 = [2, 2, 5, 7, 'as', '吃喝']
const a = (x, y) => {
let arr = x.length > y.lenght ? x : y
let list = arr.filter((v) => (x.length > y.lenght ? y : x).includes(v))
console.log(list)
}
a(nums1, nums2)

benzhemin · 2023-02-19T13:50:19Z

const intersection = (itemListA, itemListB) => {
    // convert to map
    const mapA = new Map();
    itemListA.forEach(key => {
        if (mapA.has(key)) {
            mapA.set(key, mapA.get(key) + 1);
        } else {
            mapA.set(key, 1);
        }
    });

    const intersectionList = [];

    itemListB.forEach(key => {
        if (mapA.has(key) && mapA.get(key) > 0) {
            intersectionList.push(key);
            const value = mapA.get(key);
            mapA.set(key, value - 1);
        }
    });

    return intersectionList;
}

const nums1 = [1, 2, 2, 1], nums2 = [2, 2, 2, 1, 1, 1];

const interList = intersection(nums1, nums2);
console.log(interList);

1242793152 · 2023-03-29T00:40:32Z

let arr0 = [1, 2, 3, '5', '你好啊', 7],
        arr1 = [2, 7, 9, 3, 'hello', '你好啊', 120];

这道题不是工程题，是道算法题。~~求的是两个数组的最长公共子序列~~ (子序列要求顺序，交集不需要）。所以上面用一个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 = [2,3,1,2,2,3],arr2 = [2,1,2,3,4]
function common1(arr1,arr2){
let result = []
let obj = arr1.reduce((pre,cur)=>{
pre[cur] == undefined ? pre[cur] = 1 : pre[cur]++
return pre
},{})
arr2.forEach(ele=>{
if(obj[ele]){
result.push(ele)
obj[ele]--
}
})
return result
}
console.log(common1(arr1, arr2)) //[2, 1, 2, 3]
console.log(common1(arr2, arr1)) //[2, 3, 1, 2]

    function common2(arr1,arr2){
      let result = []
      let deepArr1 = JSON.parse(JSON.stringify(arr1))
      let deepArr2 = JSON.parse(JSON.stringify(arr2))
      deepArr2.forEach(ele=>{
        deepArr1.indexOf(ele) != -1 ? result.push(...deepArr1.splice(deepArr1.indexOf(ele),1)) : ''
      })
      return result
    }
    console.log(common2(arr1, arr2))   //[2, 1, 2, 3]
    console.log(common2(arr2, arr1))   //[2, 3, 1, 2]

chthu · 2023-03-31T08:20:28Z

const test = (arr1: any, arr2: any) => {
const [newArr1, newArr2] = [arr1, arr2].sort((a, b) => a.length - b.length)
return newArr1.filter((v) => newArr2.includes(v))
}

xing-zlear · 2023-05-09T04:05:57Z

思路：取交集，如果在nums2中找到同样的元素，得把此元素从nums2中剔除，以防下次又匹配成功。

function common(nums1, nums2) {
	let result = []
	nums1.forEach(item => {
		nums2.indexOf(item) !== -1 && result.push(...nums2.splice(nums2.indexOf(item), 1))
	})
	return result
}
const res = common([1,2,2,1], [2,2])
console.log(res)

hanzehua666 · 2023-05-25T07:56:48Z

/**
 * 思路：使用一个哈希表map来记录arr1中每个数字出现的次数，先遍历arr1数组，对于每个数字，如果它已经在哈希表中，则将其出现次数加1；
 * 否则，将其添加到哈希表，并将出现次数初始化为 1。然后遍历arr2数组，对于每个数字，检查它是否在哈希表中，并且其出现次数大于 0。
 * 如果满足条件，则将该数字添加到结果数组中，并减少哈希表中该数字的出现次数最后。最后，返回结果数组。
 */
const num1 = [1, 2, 2, 1, 3];
const num2 = [2, 2, 1, 3, 1, 1];

const intersectionFn = (arr1, arr2) => {
  const map = new Map();
  const result = [];

  arr1.forEach(item => {
    if (map.has(item)) {
      map.set(item, map.get(item) + 1);
    } else {
      map.set(item, 1);
    }
  });

  arr2.forEach(item => {
    if (map.has(item) && map.get(item) > 0) {
      result.push(item);
      map.set(item, map.get(item) - 1);
    }
  });

  return result;
};
console.log(intersectionFn(num1, num2), '<<<交集');

gaohan1994 · 2023-07-05T07:34:48Z

  function intersection(array1, array2) {
    /**
     * 创建 need 遍历第一个数组生成需要对比的数据和数量
     * 创建 box 为交集
     */
    const need = new Map();
    const box = new Map();

    array1.forEach(item => {
      need.set(item, (need.get(item) ?? 0) + 1);
    });

    for (let index = 0; index < array2.length; index++) {
      const item = array2[index];

      /**
       * 遍历第二个数组
       * 如果当前元素出现在第一个数组中 && 并且已有交集中的元素数量小于第一个数组中的数量
       * 则向交集中插入当前元素 数量为之前元素数量 + 1 如果之前没有则置为1
       */
      if (need.has(item) && need.get(item) > (box.get(item) ?? 0)) {
        box.set(item, (box.get(item) ?? 0) + 1);
      }
    }

    const result = [];

    box.forEach((itemQuantity, item) => {
      result.push(...new Array(itemQuantity).fill(item));
    });

    return result;
  }


  intersection([1, 2, 2, 1], [2, 2]);

88wixi · 2023-07-19T08:07:41Z

let nums1 = [1, 2, 2, 1, 3, 8]
let nums2 = [2, 2, 3, 5]
let resultarr = []
nums1.map((item) => {
if (nums2.includes(item)) {
resultarr.push(item)
}
})
console.log(resultarr)

88wixi · 2023-07-19T08:32:55Z

function intersection(nums1, nums2) {
let map1 = new Map();
let map2 = new Map();
let result = [];

        // 统计 nums1 数组中每个元素的出现次数
        for (let num of nums1) {
            map1.set(num, (map1.get(num) || 0) + 1);
        }

        // 遍历 nums2 数组，如果元素在 map1 中存在且计数大于 0，则将其添加到结果数组中，并将计数减 1
        for (let num of nums2) {
            if (map1.has(num) && map1.get(num) > 0) {
                result.push(num);
                map1.set(num, map1.get(num) - 1);
            }
        }

        return result;
    }

    let nums1 = [2,2];
    let nums2 = [2];
    let intersect = intersection(nums1, nums2);
    console.log(intersect);

88wixi · 2023-07-19T08:38:55Z

前面确实有问题num1=[1，1]，num2=[1]得到[1,1],后面应该计算num1中的相同值个数来保证交集个数。

xiguahuibaozha · 2023-11-01T07:47:47Z

const arr1 = [1, 2], arr2 = [6,1,2,5,8,7]
const result = (arr1: number[], arr2: number[]) => {
  for(let i = arr1.length; i > 0; i--){
    for(let j = 0; j < arr1.length; j++){
      if(arr1.length - j >= i){
        const arr = arr1.slice(j, j + i)
        if(arr2.join(',').includes(arr.join(','))){
          return arr
        }
      }
    }
  }
}
console.log('result', result(arr1, arr2));

adele-ty · 2023-12-02T11:10:02Z

      if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];
      const res = [];
      nums1.map((num) => {
        if (nums2.includes(num)) res.push(num);
      });
      console.log(res);

xiezuowei · 2024-04-13T19:11:01Z

/**
 * 获取数组的交集
 * @param  {...Array} arrays 
 */
function intersection(...arrays) {
    if (!arrays || arrays.length === 0) {
        return [];
    }

    if (arrays.length === 1) {
        return arrays[0];
    }

    const arrayToMap = (array = []) => {
        const map = new Map();
        for (const val of array) {
            map.has(val) ? map.set(val, map.get(val) + 1) : map.set(val, 1);
        }
        return map;
    }

    let res = arrays[0];
    for (let i = 1; i < arrays.length; i++) {
        const tmp = [];
        const resMap = arrayToMap(res);

        for (const val of arrays[i]) {
            const count = resMap.get(val);
            if (count && count > 0) {
                tmp.push(val);
                resMap.set(val, count - 1);
            }
        }

        res = tmp;
    }

    return res;
}

console.log(intersection([1,2,2,1], [2, 2, 2]));

第 59 题：给定两个数组，写一个方法来计算它们的交集。 #102

第 59 题：给定两个数组，写一个方法来计算它们的交集。 #102

Comments

zeroone001 commented Apr 21, 2019 • edited Loading

ramey502 commented Apr 22, 2019

sgzhm4444 commented Apr 22, 2019

jefferyE commented Apr 22, 2019 • edited Loading

A0150315 commented Apr 22, 2019

yyyddc commented Apr 22, 2019 • edited Loading

Jon-Millent commented Apr 22, 2019

Molunerfinn commented Apr 22, 2019 • edited Loading

tongtannan commented Apr 22, 2019

dorseysen commented Apr 22, 2019 • edited Loading

ZodiacSyndicate commented Apr 22, 2019 • edited Loading

flynngao commented Apr 22, 2019

yeyi361936738 commented Apr 22, 2019

YouziXR commented Apr 22, 2019

Molunerfinn commented Apr 22, 2019

yeyi361936738 commented Apr 22, 2019

flynngao commented Apr 22, 2019 • edited Loading

GuoYuFu123 commented Apr 22, 2019

sogud commented Apr 22, 2019

jichenchen91 commented Apr 22, 2019

lzbSun commented Apr 22, 2019

thisisandy commented Apr 22, 2019

lpeihan commented Apr 22, 2019

ZodiacSyndicate commented Apr 22, 2019

WEBpeng5202 commented Apr 22, 2019 • edited Loading

Rashomon511 commented Apr 22, 2019 • edited Loading

Molunerfinn commented Apr 22, 2019

thisisandy commented Apr 22, 2019 • edited Loading

ZodiacSyndicate commented Apr 22, 2019

thisisandy commented Apr 22, 2019

zwmmm commented Apr 22, 2019 • edited Loading

zhuyuzhu commented May 16, 2021 • edited Loading

xld1393679430 commented May 18, 2021 • edited Loading

p992202933 commented Jun 17, 2021

yuzhuo25 commented Jun 24, 2021 • edited Loading

wangShengCool commented Jul 7, 2021

anguof commented Jul 12, 2021

gabengcuiyeye commented Aug 5, 2021

Magiskloop commented Aug 14, 2021

tchen-l commented Sep 12, 2021

xiangfei1 commented Oct 14, 2021

mygod48 commented Oct 27, 2021

yaoocheng commented Nov 12, 2021

AAA611 commented Nov 25, 2021 • edited Loading

下面都是代码，格式不太会搞。。。

时间复杂度为On(n是较短数组的长度)

fenglizhu commented Dec 22, 2021

sexnmaa commented Mar 20, 2022

johnsoncheg commented Apr 26, 2022

anissa18352869671 commented Jun 24, 2022

tanjunfeng commented Jan 3, 2023 • edited Loading

benzhemin commented Feb 19, 2023

1242793152 commented Mar 29, 2023

chthu commented Mar 31, 2023

xing-zlear commented May 9, 2023

hanzehua666 commented May 25, 2023

gaohan1994 commented Jul 5, 2023

88wixi commented Jul 19, 2023

88wixi commented Jul 19, 2023

88wixi commented Jul 19, 2023

xiguahuibaozha commented Nov 1, 2023

adele-ty commented Dec 2, 2023

xiezuowei commented Apr 13, 2024 • edited Loading

zeroone001 commented Apr 21, 2019 •

edited

Loading

jefferyE commented Apr 22, 2019 •

edited

Loading

yyyddc commented Apr 22, 2019 •

edited

Loading

Molunerfinn commented Apr 22, 2019 •

edited

Loading

dorseysen commented Apr 22, 2019 •

edited

Loading

ZodiacSyndicate commented Apr 22, 2019 •

edited

Loading

flynngao commented Apr 22, 2019 •

edited

Loading

WEBpeng5202 commented Apr 22, 2019 •

edited

Loading

Rashomon511 commented Apr 22, 2019 •

edited

Loading

thisisandy commented Apr 22, 2019 •

edited

Loading

zwmmm commented Apr 22, 2019 •

edited

Loading

zhuyuzhu commented May 16, 2021 •

edited

Loading

xld1393679430 commented May 18, 2021 •

edited

Loading

yuzhuo25 commented Jun 24, 2021 •

edited

Loading

AAA611 commented Nov 25, 2021 •

edited

Loading

tanjunfeng commented Jan 3, 2023 •

edited

Loading

xiezuowei commented Apr 13, 2024 •

edited

Loading