在数组中找到重复的数字,除了一个数字之外没有重复的数字

Question

假设有一个元素数组没有重复,除了1个数字,

ex. 1,2,13,4,7,11,2,6

如何以有效的方式找到重复的数字？我们可以在O(n)时间使用哈希表(HT)并使用如下的O(n)空间.

if(HT.Contains(item)) -> this is the duplicate
else
ht.add(item)

在空间和时间复杂性方面有更好的方法吗？

注意: 这个问题不是以下两个不同的问题的重复.

如果整数是连续的,则可以使用此链接中的解决方案如何在一个混乱的连续整数数组中找到一个复制元素

如果n个元素的数组包含从0到n-1的元素,则只有此链接具有解决方案在O(n)时间和O(1)空间中查找重复项

Answer 1

与字操作（获取/设置字）相比，对单个位的操作非常耗时（例如：获取字、获取/设置 1 位、设置字）。

如果您知道 MIN_VALUE >=0，也知道 MAX_VALUE 并且它足够小，您可以执行 Jongware 建议的操作 - 哈希表，但不是位：哈希值只是该值。

#include <stdio.h>
#include <string.h>

#define MAX_VALUE 13 +1 // +1 so we don't have do -1 in for loop

main()
{
    int i;
    int array[] = { 1,2,13,4,7,11,2,6 };
    int array_size = sizeof(array) / sizeof(array[0]);

    short flags[MAX_VALUE] = { 0 };
    for (i = 0; i < array_size; ++i) {
          if (++flags[ array[i] ] != 1) {
              printf ("duplicated %d on %d\th position", array[i], i);
          }
    }
}

而且它也不需要计算每个元素的哈希值。