Chinaunix首页 | 论坛 | 博客
  • 博客访问: 545039
  • 博文数量: 126
  • 博客积分: 2071
  • 博客等级: 大尉
  • 技术积分: 1522
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-24 16:09
文章分类
文章存档

2013年(8)

2012年(37)

2011年(80)

2010年(1)

分类:

2011-11-21 12:16:28

原文地址:找出数组中重复的数 作者:renjian2011

来自互联网,有改动。

问题:数组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]。

  1. int do_dup(int arr[],int NUM)
  2. {
  3.         int i = 0;
  4.         int *arrayflag = malloc( NUM * sizeof(int) );
  5.         while(i++ < NUM)
  6.                 arrayflag[i] = 0;

  7.         for(i=0; i<NUM; i++)
  8.         {
  9.                 if( 0 == arrayflag[ arr[i] ] )
  10.                        arrayflag[arr[i]] = 1; // 置出现标志
  11.                 else
  12.                        break;
  13.         }
  14.         free(arrayflag);
  15.         return arr[i];
  16. }

三、固定偏移标志法

同样是访问过后做标记的思想,为克服申请了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。

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

  1. int do_dup(int arr[], int NUM)
  2. {
  3.     int i, k = 0;
  4.     for(i=0; i<NUM; ++i)
  5.     {
  6.         // get new index K
  7.         if(arr[i] >= NUM)
  8.             K = arr[i] - NUM; //has marked, recover
  9.         else
  10.             K = arr[i];

  11.         // mark or duplicate
  12.         if(arr[K] < NUM)
  13.         {
  14.             arr[K] += NUM; // mark it
  15.         }
  16.         else
  17.         {
  18.             printf("got duplicate %d.\n", a[i]);
  19.             return a[i];
  20.         }
  21.     }
  22. }

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

  1. bool dup(int array[],int n)
  2. {
  3.      for(int i=0;i<n;i++)
  4.      {
  5.          if(array[i]>0) //可以以此作下标去判断其他值
  6.          {
  7.                if(array[array[i]]<0)
  8.                {
  9.                        return array[i];//已经被标上负值了,有重复
  10.                }
  11.                else
  12.                {
  13.                        array[array[i]]= -array[array[i]]; //否则标记为负
  14.                 }

  15.          }
  16.          else // |array[i]|代表的值已经出现过一次了
  17.          {
  18.                if(array[-array[i]]<0)
  19.                {
  20.                    return -array[i];//有重复
  21.                }
  22.                else
  23.                {
  24.                    array[-array[i]]=-array[-array[i]];
  25.                }
  26.           }
  27.      }
  28.       return -1;//没有重复
  29. }

  30. //用于修复数组
  31. void restorearray(int array[],int n)
  32. {
  33.         for(int i=0;i<n;i++)
  34.         {
  35.                 if(array[i]<0)array[i]= -array[i];
  36.         }

  37. }

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

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

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

 

阅读(14662) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~