java - 查找列表是否包含另一个列表的每个元素的最佳优化方法是什么？

Question

我有两个列表:

List<String> firstList = new LinkedList<String>();
List<String> secondList = new LinkedList<String>();

我想知道一个列表的每个元素是否都包含在另一个列表中。 一个可能的解决方案是:

public boolean function(List<String> first, List<String> second)
{
first = firstList;
second = secondList
for (String item : firstList)
    {
            for (String elem : secondList)
            {
                if(elem.compareTo(item)!=0)
                return false;
            }
    }
 return true;
 }

正如我们所见，时间是二次方的。有没有办法做得更好？

Answer 1

您有一个 O(n*m) 的实现，需要 O(1) 的空间；您可以通过将第一个列表的元素添加到 HashSet<String> 来实现具有 O(m) 空间要求的 O(n+m) 实现，然后验证第二个列表的所有元素是否都存在:

Set<String> firstSet = new HashSet<String>(firstList);
for (String elem : secondList) {
    if(!firstSet.contains(item)) {
        return false;
    }
}
return true;

甚至更好

return new HashSet<>(firstList).containsAll(secondList);

(谢谢，bradimus!)

注意:您的方法使用次优比较机制:而不是调用 compareTo , 你可以调用 equals ，因为您不需要检查单词是按字母顺序排列在前面还是后面。

另一个问题是您的方法通常会返回 false什么时候应该返回 true ，因为你返回 false太早了。