java - 比较 2 个列表中的元素时如何避免 O(N^2)？

Question

我有 2 个具有相同对象类型的列表。

List A [ foo, bar, moo, woo, pee ]

List B [ bar, woo ]

我想比较这两个列表，如果名称匹配， 将其属性设置为 true。

例如，

if(ListA[1].name.equals(ListB[0].name)) { //match name 'bar' and 'bar'
    ListA[1].hasSameName = true;
}

类似的东西。

我可以写 O(N^2) 的解决方案。

for(Talent checkedTalent : ListA) {
    for(Talent filteredTalent : ListB) {
        if( checkedTalent.Id.equals(filteredTalent.Id) ) {
            filteredTalent.isSelected = true;   
        }
    }
}

可以用更有效的方式做到这一点吗？

Answer 1

对 O(n) 解决方案使用散列(假设有效的散列实现):

Set<String> ids = new HashSet<String>(ListA.size());
for(Talent checkedTalent : ListA) {
    ids.add(checkedTalent.Id);
}
for(Talent filteredTalent : ListB) {
    if (ids.contains(filteredTalent.Id)) {
        filteredTalent.isSelected = true;
    }
}