数组中重复的数字

来自互联网，有改动。

问题：数组a[N]，1至N-1这N-1个数存放在a[N]中，其中某个数重复一次。写一个函数，找出被重复的数字。时间复杂度不超过O(n)。

一、数学推导法

不重复时 sum = 1+2+...+ d + (d+1)...+N；现在less = 1+2+...+ d + d + (d+1)+...+(N-1)。

sum 和 less都有N个数，由于less中只有一个重复的数字d，则必有1 <= d <= (N-1)，sum > less。

sum - less = 0+0+...+ 0 + (-d) + 0...0 + N = ( N - d ) 。所以重复的d = N - (sum - less)。

二、标志数组法

设数组a[n] = {2,3,2,1}，2是重复数字。

把一个数组b[]初始化为"0000"，对a[]访问一位在b[]上标记一位，再次访问到时查看标志位已经被置1则发现重复。空间复杂度O(n)。 

遍历时，a[0]=2，令b[2]=1，"0010"；a[1]=3，令b[3]=1，"0011"；a[2]=2，b[2]已经==1，找到a[2]。

int do_dup(int arr[],int NUM)
{
        int i = 0;
        int *arrayflag = malloc( NUM * sizeof(int) );
        while(i++ < NUM)
                arrayflag[i] = 0;

        for(i=0; i<NUM; i++)
        {
                if( 0 == arrayflag[ arr[i] ] )
                       arrayflag[arr[i]] = 1; // 置出现标志
                else
                       break;
        }
        free(arrayflag);
        return arr[i];
}

三、固定偏移标志法

同样是访问过后做标记的思想，为克服申请了O(n)的空间的缺陷，充分利用a[N]本身值和下标的关系来做标记，把标记直接放到数组内的数值上再清除标记。时间O(n)=N，空间O(n)=1。

a[N]，里面是1至N-1。原数组a[i]最大是N-1，若a[i]=K在某处出现后，将a[K]加一次N，做标记，当某处a[i]=K再次成立时，查看a[K]即可知道K已经出现过。a[i]在程序中最大也只是N-1+N=2N-1。注意防止值溢出。

以数组{2,3,1,2}为例。所谓固定偏移，有点间接寻址的意思 :)。

a[0]=2 < 4，未标记，K=2，    a[2]=1 < 4，做标记，让a[2]= a[2]+4 = 5；                           a[1]=3 < 4，未标记，K=3，    a[3]=2 < 4，做标记，让a[3]= a[3]+4 = 6；                           a[2]=5 >= 4，还原K=a[2]-4=1，a[1]=3 < 4，让a[1]= a[1]+4 = 6；                                   a[3]=6 >= 5，还原K=a[3]-4=2, a[2]=5 >=4，不能还原，发现重复，返回a[3]=2。

下边的实现可能改变了原数组，需要恢复处理。

int do_dup(int arr[], int NUM)
{
    int i, k = 0;
    for(i=0; i<NUM; ++i)
    {
        // get new index K
        if(arr[i] >= NUM)
            K = arr[i] - NUM; //has marked, recover
        else
            K = arr[i];

        // mark or duplicate
        if(arr[K] < NUM)
        {
            arr[K] += NUM; // mark it
        }
        else
        {
            printf("got duplicate %d.\n", a[i]);
            return a[i];
        }
    }
}

四、既然利用a[N]本身值和下标的关系，可以用访问的结果K作为要标记数的索引，那么就不仅可以用NUM来标记和还原，还能更变态地使用int数据类型的符号位来标记，数据本身是正数，不影响数据的标记和恢复。

bool dup(int array[],int n)
{
     for(int i=0;i<n;i++)
     {
         if(array[i]>0) //可以以此作下标去判断其他值
         {
               if(array[array[i]]<0)
               {
                       return array[i];//已经被标上负值了，有重复
               }
               else
               {
                       array[array[i]]= －array[array[i]]; //否则标记为负
                }

         }
         else // |array[i]|代表的值已经出现过一次了
         {
               if(array[-array[i]]<0)
               {
                   return -array[i];//有重复
               }
               else
               {
                   array[-array[i]]=－array[-array[i]];
               }
          }
     }
      return -1;//没有重复
}

//用于修复数组
void restorearray(int array[],int n)
{
        for(int i=0;i<n;i++)
        {
                if(array[i]<0)array[i]= －array[i];
        }

}

但是上述问题并不能处理一般的数组中的重复数字，如问题2。

问题2：有一个数组t[100]，存放了int型的正整数（若含有负数呢？），用效率较高的算法把重复数字去掉。例如数组{1,2,2,6,3,5,6,6}变成{1,2,3,5,6}。

每次读一个元素就先在HashMap里面find，如果找到，就跳过这个数。如果没有找到,则在HashMap里面insert这个数，并且把这个数加入到要返回的数组中。会额外的使用一块HashMap的内存。