減少對象

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