如何降低两个列表算法中搜索的复杂度？

我必须在两个列表中找到一些常见项目。我不能排序它，顺序很重要。必须在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

如何降低两个列表算法中搜索的复杂度？

回答

相关问题