如何在 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 。

我无法弄清楚这一点。请帮忙。

原文由 TechnoCorner 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

如何解决它的方法之一。

 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(JSON.stringify(newArr));

 .as-console-wrapper { max-height: 100% !important; top: 0; }

原文由 kind user 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

我不知道 reduce 在这里会有什么帮助，但你可以使用 Map 在 O(n) 中完成相同的任务

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

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

// For values in 'b', 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());

console.log(JSON.stringify(result));

 .as-console-wrapper { max-height: 100% !important; top: 0; }

因为 Map 访问和更新是 O(1) （平均而言 - 因为哈希冲突和重新哈希，它可能会更长），这使得 O(n+m) n a65f （ --- and m are the lengths of a and b respectively; the naive solution you gave would be O(n*m) using the same n 和 m 的含义）。

原文由 ShadowRanger 发布，翻译遵循 CC BY-SA 4.0 许可协议