减少对象

Question

的列表之间的比较复杂度O^2我有对象的两个列表：

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）。

我不确定列表是否总是按默认排序，但从我所看到的（列表1和列表2）总是按值排序。

实施例：

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的值，并且它concating到list1之前过滤由所述组中的值list2：

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);

Answer 2

您可以使用单个循环并将该值存储在一个集合中供以后检查。复杂性：O（n）。

var list1 = [{ value: 'X' }, { value: 'Y' }, { value: 'C' }, { value: 'Z' }], 
 
    list2 = [{ value: 'A' }, { value: 'B' }, { value: 'C' }, { value: 'D' }], 
 
    list3 = list1 
 
     .concat(list2) 
 
     .filter((s => ({ value }) => !s.has(value) && s.add(value))(new Set)); 
 

 
console.log(list3);

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