如何减少在两个列表算法中搜索的复杂性？

Question

我需要在两个列表中找到一些共同的项目。我不能对其进行排序，顺序很重要。必须找出有多少个来自secondList的元素出现在firstList中。现在看起来像下面这样：

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

此算法的复杂度为n x 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]

迭代到列表A中的下一个元素j-1（意思是 for(int z=0;z<j-1;z++)）。 我不确定，我表达清楚了吗？ 允许重复。

- Janusz Lece

---

列表的最大可能大小是多少？ - Swapnil

你能给一个例子吗？这个描述不太清楚：“必须找出secondList中有多少个元素出现在firstList中。” <-- 这是否包括重复项？如果第一个列表是{1, 4, 3, 4}，第二个列表是{4, 4}，它应该如何运作？ - fge

如果您不打算涉及O(n)存储，那么在理论上您不能比O(n^2)更好地解决此问题。 - Marko Topolnik

你能解释一下吗？你想知道一个列表中有多少个元素出现在另一个列表中，为什么在这种情况下顺序很重要？ - user902383

@Swapnil 最大尺寸不超过2^20。 - Janusz Lece

Answer 1

我的方法是 - 把第一个数组中的所有元素放进一个HashSet，然后对第二个数组进行迭代。这将把复杂度降低到两个数组长度之和。它的缺点是需要额外的内存，但除非你使用更多内存，否则我认为你无法改进你的暴力解决方案。

编辑：为了避免进一步争议。如果你允许第一个数组中有重复项，并且你真正关心第二个数组中的元素与第一个数组中的元素匹配的次数，请使用HashMultiSet。

- Ivaylo Strandjev

---

不幸的是，HashSet 会吞噬重复项。 - fge

@fge，您只关心一个元素是否同时出现在两个数组中，而不关心它出现的次数！ - Ivaylo Strandjev

@fge 我不同意，他说“两个共同项目”，这意味着他不关心它们“共同”了多少次。 - Ivaylo Strandjev

@ignis 不是真的 - 使用相同的方法和 HashMap 或 HashMultiMap，具体取决于语句的含义。 - Ivaylo Strandjev

@所有人，请将讨论转移到聊天室。 - Ivaylo Strandjev

Answer 2

• 将第一个列表的所有项放入一个集合中
• 对于第二个列表的每个项，测试它是否在集合中。

少于n x n的时间内解决！

编辑以取悦fge :)

您可以使用具有项目作为键和出现次数作为值的映射代替集合。

然后，对于第二个列表的每个项，如果它存在于映射中，则针对第一个列表中的每个出现（字典条目的值）执行一次操作。

- Nicolas Repiquet

---

一个 Set 可以去重，但是 OP 没有说明是否可能存在重复。 - fge

这句话有点不太合理！如果 OP 想要两个列表之间的重复项，我们并不关心其中一个列表内部的重复项，对吧？ - Nicolas Repiquet

我们确实需要这样做：这意味着此操作可能需要执行两次，而不是一次。 - fge

Answer 3

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。

- Babasaheb Gosavi

Answer 4

仅仅因为顺序很重要并不意味着您不能对任何一个列表（或两个列表）进行排序。这只意味着在您可以对任何内容进行排序之前，您必须先复制它们。当然，复制需要额外的内存，而排序需要额外的处理时间...但我猜想，所有比O(n^2)更好的解决方案都需要额外的内存和处理时间（对于建议的HashSet解决方案也是如此-将所有值添加到HashSet中会增加额外的内存和处理时间）。

对两个列表进行排序的时间复杂度为O(n * log n)，一旦列表排序完成，查找共同元素的时间复杂度为O(n)。它是否比您本地的O(n^2)方法更快取决于列表的大小。最终，只有测试不同的方法才能告诉您哪种方法最快（这些测试应该使用您最终代码中预期的实际列表大小）。

大O符号是一种不表示绝对速度的符号，它只告诉你相对速度的大小。例如，如果你有两个算法用于从输入元素集中计算一个值，一个是O(1)，另一个是O(n)，这并不意味着O(1)的解决方案总是更快。这是对大O符号的误解！它只意味着如果输入元素的数量翻倍，O(1)的解决方案仍将花费大约相同的时间，而O(n)的解决方案将花费以前的两倍时间。因此，毫无疑问，通过不断增加输入元素的数量，必定会有一个点，使得O(1)的解决方案比O(n)的解决方案更快，然而在很小的元素集合下，O(1)的解决方案可能比O(n)的解决方案更慢。

- Mecki

Answer 5

好的，如果第一个或第二个数组中没有重复项，那么这个解决方案将起作用。由于问题没有说明，我们不能确定。

首先，从第一个数组构建一个LinkedHashSet<Integer>，并从第二个数组构建一个HashSet<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();

- fge