javascript - 降低对象列表之间比较的复杂度 O^2

Question

我有两个对象列表:

list1 = [{value: 'X'}, {value: 'Y'}, ..., {value: 'Z'}];
list2 = [{value: 'A'}, {value: 'B'}, ..., {value: 'C'}];

我有这段代码，用于检查 list2 中的值是否在 list1 中。如果是，则代码不执行任何操作，如果不是，则应添加到 list1 (这将创建一个新列表 list3)。这意味着我正在两个列表之间进行并集而不保留重复值。

for (let i = list2.length-1; i >= 0; i--) {
  let item = list2[i];
  let shared = false;
  for (let j = list1.length-1; j >=0; j--) {
    let childItem = list1[j];
    if (item.value === childItem.value) {
      shared = true;
      break;
    }
  }
  if (!shared) { newValues.push(item); }
}
list3 = list1.concat(newValues);

这很好用，但我想知道是否可以改进这个 O(n*m)。

我不确定列表是否总是默认排序，但据我所知，列表(list1 和 list2)始终按值排序。

示例:

var list1 = [{value: 'bar'}, {value: 'baz'}, {value: 'foo'}, {value: 'foz'}];
var list2 = [{value: 'bar'}, {value: 'foo'}, {value: 'test'}, {value: 'testz'}];
var list3 = union(list1, list2);
list3 = [{value: 'bar'}, {value: 'baz'}, {value: 'foo'}, {value: 'foz'}, {value: 'test'}, {value: 'testz'}];

Answer 1

创建 list1 的一组值，并根据该集中的值过滤 list2，然后将其连接到 list1:

var list1 = [{value: 'bar'}, {value: 'baz'}, {value: 'foo'}, {value: 'foz'}];
var list2 = [{value: 'bar'}, {value: 'foo'}, {value: 'test'}, {value: 'testz'}];

const union = (list1, list2) => list1.concat(
  list2.filter(function({ value }) { // filter list2
    return !this.has(value); // filter out items which value is in the set
  }, new Set(list1.map(({ value }) => value))) // the set of list1 values
);

const list3 = union(list1, list2);

console.log(list3);