数组双重遍历

Question

var arr1 = [{
        id: 1,
        name: 'a'
    }, {
        id: 2,
        name: 'b'
    }, {
        id: 3,
        name: 'c'
    }, {
        id: 4,
        name: 'd'
    }, {
        id: 5,
        name: 'e'
    }, {
        id: 6,
        name: 'f'
    }];
        
    var arr2 = [{
        id: 1,
        name: 'a'
    }, {
        id: 4,
        name: 'd'
    }, {
        id: 7,
        name: 'g'
    }];

两个数组 arr1 和 arr2 求他们中 id 相同的项。有什么最优的方案吗？

Answer 1

这个完全不需要数组双重遍历，一次遍历就够了。复杂度完全可以做到：

O = arr1.length + arr2.length + min(arr.length, arr2.length);

我的方案如下：

const [minArr, maxArr] = arr1.length > arr2.length ? [arr2, arr1] : [arr1, arr2];
const tempMaxArrObj = {};
maxArr.map(item => tempMaxArrObj[item.id] = item);  // m 的复杂度
minArrIdArr = minArr.map(item => item.id);    // n 的复杂度
const result = [];
minArrIdArr.map((id) => tempMaxArrObj[id] && result.push(tempMaxArrObj[id])); // min(m, n) 的复杂度。

Answer 2

const concatArr = [...arr1, ...arr2]
const hash = {}
concatArr.forEach(obj => {
  if (hash[obj.id]) {
    // 这里就得到了两个的 name 值：
    console.log(obj.name, hash[obj.id])
  } else {
    hash[obj.id] = obj.name
  }
})

Answer 3

提供一个用 Set 求交集的方法：

arr1 = new Set(arr1.map(i => i.id));
arr2 = new Set(arr2.map(i => i.id));
let intersectionSet = new Set([...arr1].filter(x => arr2.has(x)));
console.log(intersectionSet);

Answer 4

  for(var i = 0 ; i<arr1.length;i++){
        for(var j = 0 ; j<arr2.length;j++){
            if(arr1[i].id===arr2[j].id){
                console.log(arr1[i].name,arr2[j].name);
            }
        }
    }

Answer 5

loadash intersection :

_.intersectionBy([{ 'x': 1 }], [{ 'x': 2 }, { 'x': 1 }], 'x');
// => [{ 'x': 1 }]

参考，内部代码应该也是双重便利。 https://lodash.com/docs/4.17.4

Answer 6

两个数组里面的项的id是递增的吗？