的列表之间的比较复杂度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'}];
当你说“在列表2的值是否在列表1”你的意思是,如果有的话,或者如果所有,价值观? –
我会添加一个例子来澄清 – mk2