如何降低兩個列表算法中搜索的複雜度？

我必須在兩個列表中找到一些常見項目。我不能排序它，順序很重要。必須在firstList中找到secondList中有多少元素。現在它看起來象下面這樣：如何降低兩個列表算法中搜索的複雜度？

int[] firstList; 
int[] secondList; 
int iterator=0; 
for(int i:firstList){ 
while(i <= secondList[iterator]/* two conditions more */){ 
     iterator++; 
     //some actions 
    } 
}

複雜算法的是N×N的。我儘量減少這種操作的複雜性，但我不知道如何以不同的方式比較元素？有什麼建議？

編輯： 例子：A=5,4,3,2,3B=1,2,3 我們找對B[i],A[j] 條件：時

B[i] < A[j] 
     j++

時通過一個到列表

B[i] >= A[j] 
     return B[i],A[j-1]

下一個迭代元素j-1（平均for(int z=0;z<j-1;z++)） 我不確定，我是否讓自己清楚？ 允許複製。

來源

2013-01-15 Janusz Lece

列表可能的最大尺寸是多少？ – Swapnil

你能舉個例子嗎？這並不清楚：「必須從firstList中找到secondList中有多少個元素。」 < - 包括重複嗎？如果首先是{1，4，3，4}，其次是{4,4}，它應該如何表現？ – fge

如果你不打算涉及O（n）存儲，那麼你理論上不能解決這個問題比O（n^2）更好。 –

我的方法是 - 將第一個數組中的所有元素放在HashSet中，然後對第二個數組進行迭代。這將複雜性降低到兩個陣列長度的總和。它有額外的內存缺點，但除非你使用更多的內存，我不認爲你可以改善你的蠻力解決方案。

編輯：避免就此事發生進一步爭議。如果你都不允許有重複的第一陣列中，你真正關心多少次第二數組中的元素匹配的第一個數組，使用HashMultiSet。

來源

2013-01-15 10:16:26

不幸的是，'HashSet'會吞噬 – fge

@fge你只有一個元素出現在兩個數組沒有多少次重複的關懷！ –

不知道......任擇議定書沒有具體規定，所以默認... – fge

把第一個列表的所有項目中的一組
對於第二個列表中的每個項目，測試，如果它在一組。

解決了小於n×n的！

編輯取悅FGE :)

取而代之的是一套，你可以使用地圖的項目爲重點，併爲發生值的數量。

然後在第二個列表中的每個項目，如果它在地圖上存在，每occurence在第一個列表執行你的動作一次（詞典條目值）。

來源

2013-01-15 10:17:23

一套'吞服副本，OP並沒有說是否可能出現僞裝 – fge

Doesn沒有什麼意義！如果OP想要在兩個名單之間做出選擇，我們不關心兩個名單中的一個名單，我們呢？ –

嗯，是的，我們這樣做：這意味着操作可能必須進行兩次，而不是一次。 – fge

import java.util.*; 

int[] firstList; 
int[] secondList; 
int iterator=0; 

HashSet hs = new HashSet(Arrays.asList(firstList)); 
HashSet result = new HashSet(); 

while(i <= secondList.length){ 
    if (hs.contains(secondList[iterator])) 
    { 
    result.add(secondList[iterator]); 
    } 
iterator++; 
}

結果將包含所需的通用元素。算法複雜度n

來源

2013-01-15 10:27:56

好的，如果第一個或第二個數組中沒有重複項，那麼此解決方案將工作。由於問題沒有說明，我們無法確定。

首先，從第一個陣列中構建一個LinkedHashSet<Integer>，並在第二個陣列中構建一個。

其次，保持在所述第一組僅是在所述第二組元件。

第三，遍歷第一盤並繼續：

// A LinkedHashSet retains insertion order Set<Integer> first = LinkedHashSet<Integer>(Arrays.asList(firstArray)); // A HashSet does not but we don't care Set<Integer> second = new HashSet<Integer>(Arrays.asList(secondArray)); // Retain in first only what is in second first.retainAll(second); // Iterate for (int i: first) doSomething();

來源

2013-01-15 10:29:56 fge

僅僅因爲順序很重要，並不意味着你不能既排序列表（或兩者）。這隻意味着你必須首先複製，然後才能對任何東西進行排序。當然，複製需要額外的內存和排序需要額外的處理時間......但我想所有比O（n^2）更好的解決方案都需要額外的內存和處理時間（對於建議的HashSet解決方案也是如此 - 將所有值到HashSet需要額外的內存和處理時間）。

排序兩個列表可以在O（N * log n）的時間，找到公共元素一旦列表進行排序可以在O（n）的時間。它是否比你的本地O（n^2）方法更快取決於列表的大小。最後，只有測試不同的方法才能告訴你哪種方法最快（並且這些測試應該使用最終代碼中預期的實際列表大小）。

大O符號是沒有符號，它能夠告訴你絕對速度，它只是告訴你一些關於相對速度。例如。如果你有兩個算法來計算輸入元素集的值，一個是O（1），另一個是O（n），這並不意味着O（1）解決方案總是更快。這是對Big-O符號的一個很大的誤解！這隻意味着如果輸入元素的數量增加一倍，那麼O（1）解決方案仍然需要大約一半的時間。 O（n）解決方案需要大約相同的時間。是以前的兩倍。因此，毫無疑問，通過不斷增加輸入元素的數量，O（1）解決方案將比O（n）解決方案變得更快，但對於非常小的一組元素，O（ 1）解決方案實際上可能比O（n）解決方案更慢。

來源

2013-01-15 10:38:54 Mecki

如何降低兩個列表算法中搜索的複雜度？

回答

相關問題