第 142 题：算法题 - 求多个数组之间的交集

Question

本文介绍了JS数组交集、并集、差集，分享给大家，具体如下：由于下面会用到 ES5 的方法，低版本会存在兼容，先应添加对应的 polyfill

Array.prototype.indexOf = Array.prototype.indexOf || function (searchElement, fromIndex) {
  var index = -1;
  fromIndex = fromIndex * 1 || 0;
  for (var k = 0, length = this.length; k < length; k++) {
    if (k >= fromIndex && this[k] === searchElement) {
      index = k;
      break;
    }
  }
  return index;
};

Array.prototype.filter = Array.prototype.filter || function (fn, context) {
  var arr = [];
  if (typeof fn === "function") {
    for (var k = 0, length = this.length; k < length; k++) {
      fn.call(context, this[k], k, this) && arr.push(this[k]);
    }
  }
  return arr;
};

依赖数组去重方法：

// 数组去重
Array.prototype.unique = function() {
  var n = {}, r = [];
  for (var i = 0; i < this.length; i++) {
    if (!n[this[i]]) {
      n[this[i]] = true;
      r.push(this[i]); 
    }
  }
  return r;
}

交集

交集元素由既属于集合A又属于集合B的元素组成

Array.intersect = function(arr1, arr2) {
  if(Object.prototype.toString.call(arr1) === "[object Array]" && Object.prototype.toString.call(arr2) === "[object Array]") {
    return arr1.filter(function(v){ 
     return arr2.indexOf(v)!==-1 
    }) 
  }
}
// 使用方式
Array.intersect([1,2,3,4], [3,4,5,6]); // [3,4]

并集

并集元素由集合A和集合B中所有元素去重组成

Array.union = function(arr1, arr2) {
  if(Object.prototype.toString.call(arr1) === "[object Array]" && Object.prototype.toString.call(arr2) === "[object Array]") {
    return arr1.concat(arr2).unique()
  }
}
// 使用方式
Array.union([1,2,3,4], [1,3,4,5,6]); // [1,2,3,4,5,6]

差集

A的差集：属于A集合不属于B集合的元素

B的差集：属于B集合不属于A集合的元素

Array.prototype.minus = function(arr) {
  if(Object.prototype.toString.call(arr) === "[object Array]") {
    var interArr = Array.intersect(this, arr);// 交集数组
    return this.filter(function(v){
      return interArr.indexOf(v) === -1
    })
  }
}
// 使用方式
var arr = [1,2,3,4];
arr.minus([2,4]); // [1,3]

Answer 1

function getSameItem(arr, ...rest) {
	return arr.filter(item => rest.every(restArr => restArr.indexOf(item) > -1))
}

Answer 2

const p1 = [
{
id: 123
},
{
id: 124
},
{
id: 125
},
]
const p2 = [
{
id: 124
},
{
id: 125
},
{
id: 125
},
{
id: 126
},
]
const p3 = [
{
id: 125
},
{
id: 128
},
{
id: 128
},
]
let a = intersections([p1, p2, p3])
console.log(a)

function intersections(options) {
  if (!Array.isArray(options) || !options.length) return;
  let arrLength = options.length;
  let result = [];
  let cacheFirstResult = [];
  let arr = [];
  let l = 0;
  let obj = {};
  let obj1 = {}
  
  function initState(arr) {
    let l = arr.length;
    while(l) {
      l--;
      obj1[arr[l].id] = true;
    }
  }
  initState(options[0])

  while (arrLength--) {
    arr = options[arrLength];
    l = arr.length;
    while (l) {
      l--;
      if (obj1[arr[l].id]) {
        obj[arr[l].id] = true;
        if (arrLength === options.length - 1)
          cacheFirstResult.push(arr[l])
      }
    }
    obj1 = {...obj}
    obj = {}

  }
  return cacheFirstResult.filter(v => {
    if (Object.keys(obj1).indexOf(v.id.toString()) !== -1) return v;
  })
}

Answer 3

var arr=[1,2,3]
var arr2=[2,3,4,5]
var arr3 = [3,4,5,6]
var arr4 = [6,4,1,2]
function selectArr(arr1,arr2){
var narr = [];
for(var i = 0; i<arr1.length; i++){
for(var j = 0; j<arr2.length; j++){
if(arr1[i]===arr2[j]&&narr.indexOf(arr2[j])==-1){
narr.push(arr2[j])
}
}
}
return narr
}

function setArr(...arg){
if(arg.length===0){
return false
}
if(arg.length===1){
return arg[0]
}
if(arg.length>1){
for(var i = 1; i<arg.length; i++){
arg[i] = selectArr(arg[i-1],arg[i])
}

}
return arg[arg.length-1];
}
console.log(setArr(arr2,arr3))

Answer 4

如果是对象数组上面是不是好多都不管用了

Answer 5

function getSamePart() {
    let samePart = [], countMap = new Map();
    let args = [...arguments], len = args.length;
    args.reduce((arr, cur) => {
        return Array.isArray(cur) ? arr.concat(cur) : arr;
    }, []).forEach(item => {
        countMap.has(item) ? 
                 countMap.set(item, countMap.get(item) + 1) : countMap.set(item, 1)
    })
    for(let item of countMap) {
        if(item[1] >= len) {
            samePart.push(item[0])
        }
    }
    return samePart;
}
getSamePart(['1', '2', 1,2,3], ['1','2',1,2], ['1','2',3,4,5]);    // ['1', '2']

Answer 6

Clarify

Since the description kind of loose, So Let's make it clear.

Suppose that, all the list are unique , eg: [1,2,2,3] is not allow.Otherwise the solution could be quiet ugly.

Concise Solution - reduce

initially, we can set the answer to be the very first item of the list.

eg: [1,2,3], [1,2,3,5], [1] , we take [1,2,3] as the initial value(the answer can't be greater than it). then we keep filtering repeatedly

If U'r not familar with reduce, PLZ check the MDN Doc

const intersection = (...list) => list.reduce((acc, cur) => acc.filter(ele => cur.includes(ele)))

// test
intersection([1,2,3], [1,2,3,5], [1]) // [1]

More efficient and Easy to understand

• track the repeating count, store into Map as [k=item, v=count]
• finally, remove all the items which repeating counts not equals to the size of the list(WHY?)

function intersection(...list) {
  const mapper = new Map();
  const res = [];
  for (ele of list) {
    for (n of ele) {
      if (mapper.get(n) === void 0) {
        mapper.set(n, 1);
      } else {
        mapper.set(n, mapper.get(n) + 1);
      }
    }
  }

  for ([k, cnt] of mapper.entries()) {
    if (cnt === list.length) res.push(k);
  }

  return res;
}

// test
intersection([1,2,3], [1,2,3,5], [1]) // [1]

Thanks for your reading, if like it, Give Me a thumb up

Answer 7

处理数组

var a = [1, 2, 3, 5]
var b = [2, 4, 5, 1]
var c = [1, 3, 5]
var intersect
function fn(...arg){
  intersect =  arg.reduce((total,next)=>{return total.filter(item=>next.includes(item))})
}
fn(a,b,c)
console.log(intersect)
// [1,5]

处理数组和类数组（有iterable接口的数据结构）

var intersect
function fn2 (...arg){
    intersect = arg.reduce((total,next)=>{return [...total].filter(item=>new Set(next).has(item))})
}
var a = [1, 2, 3, 5]
var b = [2, 4, 5, 1]
var c = [1, 3, 5]
fn2(a,b,c)
console.log(intersect)
// [1,5]

a = new Set([1, 2, 3, 5])
b = new Set([2, 4, 5, 1])
c = new Set([1, 3, 5])
fn2(a,b,c)
console.log(intersect)
//[1,5]

Answer 8

function intersection(){
	let min_arr=arguments[0],intersect=[];
	for (let i=0;i<arguments.length;i++) {
		if(min_arr.length > arguments[i].length){ min_arr = arguments[i];}
	}
	for(let i=0;i<min_arr.length;i++){
		let flag = true;
		for (let j=0;j<arguments.length;j++) {
			if(!arguments[j].includes(min_arr[i])){
				flag = false;break;
			}
		}
		if(flag){ 
			if(!intersect.includes(min_arr[i])){ 
				intersect.push(min_arr[i]) 
			}
		}
	}
	return intersect
}
let arr = [1,2,3,4,5,6,7,8,9,10,10],arr1=[5,4,2,9,3,7,21],arr2=[9,3,5,4,11,3];
console.log(intersection(arr,arr1,arr2)) // [9, 3, 5, 4]

Answer 9

输入的数组有可能出现重复数据,需要多一步判断;如果输入的是集合,就不用这么复杂了

function intersectN(...arrs) {
    if (arrs.length === 1) return arrs[0];
    if (arrs.length === 2) return intersect2(...arrs);//如果只有两个 无需reduce 直接求
    return arrs.reduce((a, b) => b = intersect2(a, b))
}

function intersect2(nums1, nums2) {
    //求两个数组的交叉数组
    let res = [];
    let obj = toMap(nums1);
    for (let i of nums2) {
        if (obj[i]) {
            res.push(i)
            obj[i]--
        }
    }
    return res;
}

function toMap(arr) {
    //辅助函数  用于将数组转成map 键值分别是元素和其数量
    let obj = {}
    for (let i of arr) {
        if (obj[i]) obj[i]++
        else obj[i] = 1
    }
    return obj
}

let arr1 = [1, 2, 3, 4, 5, 6, 7, 1, 5]
let arr2 = [3, 5, 4, 1, 5]
let arr3 = [5, 7, 1, 3, 1, 5]

console.log(intersectN(arr1, arr2, arr3)) //[ 5, 1, 3, 5 ] 

Answer 10

const arr1 = [1, 2, 3];
const arr2 = [3, 4, 5];
const arr3 = [3, 6, 7];
const handle = (...arr) => {
  return arr.reduce((rst, ele, i) => {
    return rst.filter(item => ele.includes(item));
  });
}

handle(arr1, arr2, arr3);

Answer 11

function intersection(...args){
if(args.length == 0) return [];
if(args.length == 1) return args[0];
let arr = [];
args.forEach((item)=>{
arr = arr.concat([...item]);
})
// 并集
// return new Set(arr);

// 交集
let obj = {};
let result = [];
for(let i in arr){
	if(obj[arr[i]]){
		result.push(arr[i])
	}else{
		obj[arr[i]] = true;
	}
}
return result;

}
intersection([1,2,3],[2,3]) // [2,3]

Answer 12

let array1 = [1,2,3,4,5,6];
let array2 = [2,3,4,5,6,8,9];
let array3 = [4,5,6,7,8,9]
console.log(getIntersection(array1, array2, array3));
function getIntersection(){
let result = [];
let obj = {};
let array = [].slice.apply(arguments)
for(let i = 0; i < array.length; i++) {
let arrayItem = array[i]
for(let n = 0; n < arrayItem.length; n++) {
if (obj[arrayItem[n]]) {
obj[arrayItem[n]] = obj[arrayItem[n]] + 1
} else {
obj[arrayItem[n]] = 1
}
}
};
for(let item in obj) {
if(obj[item] > 1) {
result.push(item)
}
};
return result;
};

Answer 13

let getMix = arr => {
	return arr.reduce((total, item, index) => {
        if (index === 0) {
            return [...total, ...item]
        }
        else {
            return total.filter(v => item.includes(v))
        }
    }, [])
}
getMix([[1],[1,2],[1,3]]) //[1]

Answer 14

function intersect(...args) {
  if (args.length === 0) {
    return []
  }

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

  return args.reduce((result, arg) => {
    return result.filter(item => arg.includes(item))
  })
}

Answer 15

let setData1 = [1, 2, 3, 4],
  setData2 = [2, 3, 4, 9, 19, 91];

function mixedArr(...args) {
  let res = new Set(args[0]);
  if (args.length < 2) {
    return args[0];
  }
  for (let i = 1; i < args.length; i++) {
    const item = args[i];
    if (Object.prototype.toString.call(item).slice(8, -1) === 'Array') {
      let _arr = item.filter(e => res.has(e));
      if (_arr != [...res]) {
        res = new Set(_arr);
      }
    }
  }

  return [...res];
}

mixedArr(setData1, setData2, [2, 3]);

Answer 16

let a = new Set([1, 2, 3]);
let b = new Set([4, 3, 2]);
let intersect = new Set([...a].filter(x => b.has(x)));
// set {2, 3}

Answer 17

142