4

我必须在两个列表中找到一些常见的项目。我无法对其进行排序，顺序很重要。必须找出有多少个元素secondList出现在firstList. 现在它如下所示：

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

该算法的复杂度为nxn。我试图降低此操作的复杂性，但我不知道如何以不同的方式比较元素？有什么建议吗？

编辑： 示例：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++)） 我不确定，我说清楚了吗？ 允许复制。

4

5 回答 5

5

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

编辑：避免对此事进一步争议。如果允许在第一个数组中有重复项，并且您实际上关心第二个数组中的元素与第一个数组中的数组匹配多少次，请使用HashMultiSet.

于 2013-01-15T10:16:26.957 回答
3
  • 将第一个列表的所有项目放在一个集合中
  • 对于第二个列表的每个项目，测试它是否在集合中。

不到 nxn 解决！

编辑请 fge :)

您可以使用将项目作为键并将出现次数作为值的映射来代替集合。

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

于 2013-01-15T10:17:23.703 回答
1 
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-15T10:27:56.577 回答
1

仅仅因为顺序很重要并不意味着您不能对任何一个列表（或两者）进行排序。这仅意味着您必须先复制，然后才能对任何内容进行排序。当然，复制需要额外的内存，排序需要额外的处理时间......但我猜所有优于 O(n^2) 的解决方案都需要额外的内存和处理时间（对于建议的 HashSet 解决方案也是如此 - 添加所有值到 HashSet 会花费额外的内存和处理时间）。

可以在 O(n * log n) 时间内对两个列表进行排序，一旦列表排序，则可以在 O(n) 时间内找到共同元素。它是否会比您的本机 O(n^2) 方法更快取决于列表的大小。最后，只有测试不同的方法才能告诉您哪种方法最快（并且这些测试应该使用最终代码中预期的实际列表大小）。

Big-O 符号不是告诉你任何关于绝对速度的符号，它只告诉你一些关于相对速度的东西. 例如，如果您有两种算法来计算输入元素集的值，一种是 O(1)，另一种是 O(n)，这并不意味着 O(1) 解决方案总是更快。这是对 Big-O 表示法的一个大误解！这仅意味着如果输入元素的数量增加一倍，O(1) 解决方案仍将需要大约。相同的时间，而 O(n) 解决方案将花费大约。时间是以前的两倍。所以毫无疑问，通过不断增加输入元素的数量，一定有一个点 O(1) 解决方案将变得比 O(n) 解决方案更快，但是对于非常小的一组元素，O( 1) 解决方案实际上可能比 O(n) 解决方案慢。

于 2013-01-15T10:38:54.840 回答
0

好的，所以如果第一个或第二个数组中没有重复项，则此解决方案将起作用。由于问题没有说明，我们无法确定。

首先，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();
于 2013-01-15T10:29:56.440 回答