沒有完整遍歷的兩個列表中的公共元素

如何在兩個列表中找到公共元素而不實際瀏覽列表中的每個元素？我的意思是不使用通常的遍歷方法，我們傾向於將一個元素與整個列表進行比較。沒有完整遍歷的兩個列表中的公共元素

其他細節：

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

沒有完整遍歷的兩個列表中的公共元素

回答

相關問題