java - 没有完全遍历的两个列表中的共同元素

Question

我怎样才能在两个列表中找到共同的元素，而无需实际遍历两个列表中的每个元素？我的意思是不使用通常的遍历方法，我们倾向于将一个元素与整个列表进行比较。

额外细节：

1.列表排序

2.想通过遍历第二个列表中的最少元素来找到共同元素

Answer 1

List<Integer> list1 = new ArrayList<Integer>();

List<Integer> list2= new ArrayList<Integer>();

List<Integer> list3 = new ArrayList<Integer>(list2);

list3.retainAll(list1);

list3将只有list1和的共同元素list2。

这只是一种明显遍历列表的优化库方法。

Answer 2

list.retainAll()

注意：会在cover下遍历，不遍历是不行的

Answer 3

我假设您的意思是您不想为第一个列表中的每个元素完全遍历第二个列表。

一种方法是对两个列表进行排序，然后同时通读它们，前进或其他迭代器以查找不匹配并且两者都用于匹配。

另一种方法是对一个列表进行排序，然后对另一个列表中的每个元素进行二进制搜索。

Answer 4

您似乎在要求 O(n) 解决方案，而不是在外部和内部循环中遍历列表的天真 O(n^2) 解决方案。

一种方法是遍历其中一个列表并将其元素放入哈希表中。然后，遍历另一个列表，对于每个元素，检查该元素是否存在于哈希表中。这将是一个 O(n) 解决方案，但当然会占用空间。