在O(N)时间内查找数组中的重复项

Question

有没有一种方法可以在O（N）时间内找到由N个元素组成的数组中所有重复的元素？

示例：

输入：11, 29, 81, 14, 43, 43, 81, 29

输出：29, 81, 43

对输入进行排序并进行线性扫描以检测重复会破坏顺序并给出输出：29，43，81。

通过按照给定数组对索引数组{0、1、...、N-1}进行“按键排序”，得到{1、4、2}，然后对结果集合的索引进行排序以得到{1、2、4}，将给我们{29、81、43}，但这需要O（N logN）时间。

有没有一种O（N）算法来解决这个问题？

附言：我忘了添加：我不想使用哈希表。 我正在寻找一个非哈希解决方案。

- alpha_cod

---

如果空间不受限制，可以将每个元素存储在哈希表中。当发生冲突时，就会出现重复的元素。 - Anurag

@Anurag：你所说的哈希具体是指什么？ - CB Bailey

@Charles Bailey：我认为他的意思是map。 - Mark Byers

@Charles：没有，不了解值的范围！ - alpha_cod

为什么你要寻找一个非哈希解决方案？ - Mahmoud Al-Qudsi

Answer 1

我认为一个很好的解决方案（内存使用较少，可以立即确定一个条目是否已经被查看，从而保留顺序，并具有线性复杂度）就是trie树。

如果您将每个数字（从最高位开始）作为节点插入到trie树中，您可以以O(mN)的复杂度完成此操作，其中m是10进制数字中数值的平均长度。

您只需要循环遍历所有条目并将它们插入trie树。每次发现元素已经存在时，跳过该元素并继续下一个。与我的上一个答案中的基数排序不同，这种方法中的重复项会立即被发现，而不是在最后一次迭代之前。

我不确定在这里使用后缀树是否有益处，因为输入到trie树中的字符的“基数”仅为10（与ANSI字符串的基数-128相比）。但这是可能的。

- Mahmoud Al-Qudsi

---

不用谢。还有，特别感谢你昨晚对我的耐心，@amit！ - Mahmoud Al-Qudsi

使用trie使算法的时间复杂度为O(N log N)。更糟糕的是，所有trie实现与Kaganar提出的哈希映射相比都非常慢。如果你想要速度，就使用他的答案（真正的O(N)）。 - cmaster - reinstate monica

Answer 2

如果您的输入都是小整数，您可以使用计数排序（counting sort），它在O(n)时间内运行，并且需要O(m)空间，其中m是可能输入范围的大小。

作为一种空间优化，只需使用位数组并使用单个位（而不是计数）来存储您之前是否见过该项即可。

- Mark Byers

---

执行此操作将返回重复的元素。要按原始顺序获取这些元素：使用位向量存储哪些元素是重复项，并在原数据上进行另一个线性扫描，输出重复的元素，仍然是O(n)，并提供所需顺序中的元素。 - amit

Answer 3

听起来你不想分配任何额外的空间。然而，哈希表仍然是速度最快的解决方案。实际上，对于像整数这样的简单数据，大多数哈希表实现都因其一种解决方案适用所有情况的特性而显得过于臃肿，我会根据我的需求自己编写。当你需要将慢速代码转换为快速代码时，它可以在相对较小的工作量下实现。

另外，如果你反对哈希表的原因是它们破坏了顺序，那么也许你可以使用一种不同的方式来获取期望的O(n)并保持顺序：

创建一个哈希表，将你的数组元素映射到两个位作为从零到三的计数字段，并将30位作为元素数组的索引。除非你的数组中有超过十亿个值，否则30位就足够了。这样你的哈希值只是一个32位字。

遍历数组中的元素。如果一个元素不在哈希表中，则将该值插入哈希表并将计数字段设置为零。存储时无论索引部分是什么都没关系。如果元素在哈希表中且计数字段为零，则将其增加到1并将元素索引与新的计数字段值一起存储。如果计数字段已经为1或更大，则将其设置为2并且不要触碰存储的索引——保持它不变。

再次遍历数组中的元素。查找每个元素，如果其索引是存储的索引，并且相关联的计数字段大于零，则打印出来。

这应该以正确的顺序为你提供所需内容，并且时间复杂度为O(n)。但是，它使用了哈希表，而你似乎不希望使用哈希表，原因未知。我强烈建议你接受这种解决方案或者解释限制，以便获得更准确的目标解决方案。

- Kaganar

Answer 4

如果您知道最大值，可以这样做：
创建一个长度为最大值的单独数组。

 int[max] secondarray;

    for(int i=o;i<arrayFirst.length;i++){
        if(secondarray[arrayFirst[i]]==0){
            secondarray[arrayFirst[i]]==arrayFirst[i];
         }else{
             result.add(arrayFirst[i]);
          }
     }

- Jayantha Lal Sirisena

Answer 5

 void printRepeating(int arr[], int size)
 {
 int i;
   printf("The repeating elements are: \n");
 for (i = 0; i < size; i++)
 {
 if (arr[abs(arr[i])] >= 0)
  arr[abs(arr[i])] = -arr[abs(arr[i])];
 else
  printf(" %d ", abs(arr[i]));
 }
  }

- Rajesh M

Answer 6

你可以在O(n)的时间复杂度内完成这个操作，但需要将数组转换为整数类型。所需的空间大小大致为-2^32到2^32的数量级。

你需要做的是找到原始数组（arrayorig）的最大值和最小值，然后创建两个新数组（arraynew+）和（arraynew-）。

如果arrayorig中的所有值都是正数，则(arraynew+)的大小将为max(arrayorig)-min(arrayorig)，否则(arraynew+)的大小将为max(arrayorig)。

如果所有值都是正数，则(arraynew-)的大小为零，否则它们将等于min(arrayorig)的绝对值。

然后，您可以遍历arrayorig并将值加1到(arraynew-)或(arraynew+)的索引处，如果值为正，则应将其增加到(arraynew+)，否则如果值为负，则应将其增加到(arraynew-)的索引处，该索引等于arrayorig的绝对值。

然后，(arraynew+)和(arraynew-)中所有值>1的索引就是arrayorig的不同值。

- Igoy

Answer 7

查找重复项和排序同样困难。最好的方法是利用输入的某些属性，以便获得 O(N) 的排序。

- hugomg

---

通常情况下，识别重复元素需要进行O(N^2)操作，但在这个问题中，整数必须在数组索引范围内。你可以利用这个属性通过一种巧妙的方法来解决。将数字放置在它们在索引上所属的位置上，并找出错位的元素，就像从帽子里变出兔子一样神奇。 - Eric Leschinski