javascript - 如何使用相同的键聚合 2 个 json 数组的所有列

Question

我想从

var var1 = [
  {key:'key1',value1:'value11'},
  {key:'key2',value1:'value12'}
];

var var2 = [
  {key:'key1',value2:'value21'},
  {key:'key2',value2:'value22'}
];

到这里

var var3 = [
  {key:'key1',value1:'value11',value2:'value21'},
  {key:'key2',value1:'value12',value2:'value22'}
];

最简单的方法是什么？

Answer 1

较慢的解决方案

一种解决方案是仅迭代 array1，并且对于每个对象，如果 array2 中已存在带有其键的对象，则将其合并。

此解决方案将具有恒定的空间，但时间为二次O(arr1.length) * O(arr2.length)，因为对于 array1 中的每个对象，我们都在 array2 中搜索匹配项。

var var1=[{key:"key1",value1:"value11"},{key:"key2",value1:"value12"}],var2=[{key:"key1",value2:"value21"},{key:"key2",value2:"value22"}];

// O(N*M) time, O(1) space
function mergeQuadratic(arr1, arr2) {
  const result = [];

  arr1.forEach(obj1 => {
    // try to find a match for the current arr1 object by searching through arr2
    const obj2 = arr2.find(obj2 => obj2.key === obj1.key);

    // if we found a match, we can merge these two objects
    if (obj2) {
      result.push(Object.assign({}, obj1, obj2));
    }
  });

  return result;
}

console.log(mergeQuadratic(var1, var2));

ES5 版本:

var var1=[{key:"key1",value1:"value11"},{key:"key2",value1:"value12"}],var2=[{key:"key1",value2:"value21"},{key:"key2",value2:"value22"}];

// O(N*M) time, O(1) space
function mergeQuadratic(arr1, arr2) {
  var result = [];
  arr1.forEach(function(obj1) {
    // try to find a match for the current arr1 object by searching through arr2
    var obj2 = arr2.find(function(obj2) {
      return obj2.key === obj1.key
    });

    // if we found a match, we can merge these two objects
    if (obj2) {
      result.push(Object.assign({}, obj1, obj2));
    }
  });

  return result;
}

console.log(mergeQuadratic(var1, var2));

更快的解决方案

提高速度的一项改进是权衡一些空间并从 array2 创建映射，这样我们就可以将匹配键的查找时间减少到恒定，从而为我们提供线性运行时间 O(array1.length) + O(array2.length) 和线性空间 O(array2.length):

var var1=[{key:"key1",value1:"value11"},{key:"key2",value1:"value12"}],var2=[{key:"key1",value2:"value21"},{key:"key2",value2:"value22"}];

// O(N+M) time, O(N) space
function mergeLinear(arr1, arr2) {
  // create a map of key->obj for every object in arr2
  const map = arr2.reduce((map, curr) => {
    map.set(curr.key, curr);
    return map;
  }, new Map());

  const result = [];

  arr1.forEach(obj1 => {
    // check almost instantly if a matching object exists
    const obj2 = map.get(obj1.key); // <-- Constant time lookup

    // if we found a match, we can merge these two objects
    if (obj2) {
      result.push(Object.assign({}, obj1, obj2));
    }
  });

  return result;
}

console.log(mergeLinear(var1, var2));

ES5 版本:

var var1=[{key:"key1",value1:"value11"},{key:"key2",value1:"value12"}],var2=[{key:"key1",value2:"value21"},{key:"key2",value2:"value22"}];

// O(N+M) time, O(N) space
function mergeLinear(arr1, arr2) {
  // create a map of key->obj for every object in arr2
  var map = arr2.reduce(function(map, curr) {
    map[curr.key] = curr;
    return map;
  }, Object.create(null));

  var result = [];

  arr1.forEach(function(obj1) {
    // check almost instantly if a matching object exists
    var obj2 = map[obj1.key]; // <-- Constant time lookup

    // if we found a match, we can merge these two objects
    if (obj2) {
      result.push(Object.assign({}, obj1, obj2));
    }
  });

  return result;
}

console.log(mergeLinear(var1, var2));