我必须在两个列表中找到一些共同的项目。我无法排序它，顺序很重要。必须从 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,3 B=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++) )
我不确定，我说清楚了吗？
允许重复。
最佳答案
我的方法是 - 将第一个数组中的所有元素放入 HashSet 中，然后对第二个数组进行迭代。这将复杂度降低为两个数组的长度之和。它有占用额外内存的缺点，但除非你使用更多内存，否则我不认为你可以改进你的暴力解决方案。
编辑:避免对此事产生进一步的争议。如果您允许在第一个数组中有重复项，并且您实际上关心第二个数组中的元素与第一个数组中的元素匹配多少次，请使用 HashMultiSet。
关于java - 如何降低在两个列表中搜索算法的复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14335386/