没有完整遍历的两个列表中的公共元素

如何在两个列表中找到公共元素而不实际浏览列表中的每个元素？我的意思是不使用通常的遍历方法，我们倾向于将一个元素与整个列表进行比较。没有完整遍历的两个列表中的公共元素

其他细节：

1.列表进行排序

2.want通过遍历至少元素的数量在第二个列表

来源

2012-06-21 Nelo Angelo

'在两个实际经历过的列表中'你的意思是'没有实际经历'你使用什么方法，最坏的情况，你仍然需要遍历每个列表至少一次以验证元素是否存在。 –

list.retainAll()

注意寻找共同的元素：它将遍历下盖，你不能做遍历

来源

2012-06-21 05:27:51

实际上'List'和'Set'都有方法'retailAll（）'，所以不需要转换。 – Genzer

我假设你的意思是你不想t第二个列表完全针对第一个列表中的每个元素。

一种方法是对两个列表进行排序，然后同时读取它们，在其他迭代器上前进或失败，并进行匹配。

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

来源

2012-06-21 05:29:01

排序需要遍历所有列表 –

这个问题写得不好，我假设他们想避免O（n^2）算法。另外，它可能是一个或两个列表已经排序。 –

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唯一的共同要素。

这只是一个优化的库方法，显然会遍历列表。

来源

2012-06-21 05:29:19 Neel

你似乎在寻求O（n）解决方案，而不是在外部和内部循环中遍历列表的纯天然O（n^2）解决方案。

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

来源

2012-06-21 05:54:23

没有完整遍历的两个列表中的公共元素

回答

相关问题