如何在JavaScript中使用两个对象数组执行内部联接？

Question

我有两个对象数组:

var a = [
  {id: 4, name: 'Greg'},
  {id: 1, name: 'David'},
  {id: 2, name: 'John'},
  {id: 3, name: 'Matt'},
]

var b = [
  {id: 5, name: 'Mathew', position: '1'},
  {id: 6, name: 'Gracia', position: '2'},
  {id: 2, name: 'John', position: '2'},
  {id: 3, name: 'Matt', position: '2'},
]

我想要做的内连接这两个阵列a和b,并创建一个第三阵列像这样(如果位置属性不存在,则它变为零):

var result = [{
  {id: 4, name: 'Greg', position: null},
  {id: 1, name: 'David', position: null},
  {id: 5, name: 'Mathew', position: '1'},
  {id: 6, name: 'Gracia', position: '2'},
  {id: 2, name: 'John', position: '2'},
  {id: 3, name: 'Matt', position: '2'},
}]

我的方法:

function innerJoinAB(a,b) {
    a.forEach(function(obj, index) {
        // Search through objects in first loop
        b.forEach(function(obj2,i2){
        // Find objects in 2nd loop
        // if obj1 is present in obj2 then push to result.
        });
    });
}

但时间的复杂性是O(N^2).我怎么能这样做O(N)？我的朋友告诉我,我们可以使用减速器和Object.assign.

我无法解决这个问题.请帮忙.

Answer 1

我不知道reduce这里会有什么帮助,但你可以用a Map来完成同样的任务O(n):

var m = new Map();
// Insert all entries keyed by ID into map, filling in placeholder position
// since a lacks position entirely
a.forEach(function(x) { x.position = null; m.set(x.id, x); });

// For b values, insert them if missing, otherwise, update existing values
b.forEach(function(x) {
    var existing = m.get(x.id);
    if (existing === undefined)
        m.set(x.id, x);
    else
        Object.assign(existing, x);    
});

// Extract resulting combined objects from the Map as an Array
var result = Array.from(m.values());

因为Map访问和更新是O(1)(平均情况,由于哈希冲突和重新散列,它可能更长),这使得O(n+m)(在哪里n和m分别是长度a和b你给出的天真解决方案将O(n*m)使用相同的含义n和m).

Answer 2

解决方法之一。

const a = [
  {id: 4, name: 'Greg'},
  {id: 1, name: 'David'},
  {id: 2, name: 'John'},
  {id: 3, name: 'Matt'},
];

const b = [
  {id: 5, name: 'Mathew', position: '1'},
  {id: 6, name: 'Gracia', position: '2'},
  {id: 2, name: 'John', position: '2'},
  {id: 3, name: 'Matt', position: '2'},
];

const r = a.filter(({ id: idv }) => b.every(({ id: idc }) => idv !== idc));
const newArr = b.concat(r).map((v) => v.position ? v : { ...v, position: null });

console.log(newArr);