Chinaunix首页 | 论坛 | 博客
  • 博客访问: 239447
  • 博文数量: 62
  • 博客积分: 973
  • 博客等级: 准尉
  • 技术积分: 530
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-16 23:25
文章分类

全部博文(62)

文章存档

2013年(1)

2012年(14)

2011年(47)

分类: C/C++

2011-11-21 00:01:16

题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)

来自: http://www.cnblogs.com/mingzi/archive/2009/08/04/1538470.html                     http://blog.csdn.net/zhuxiaoyang2000/article/details/6259233

分析:首先我们考虑这个问题的一个简单版本:一个数组里除了一个数字之外,其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

这个题目的突破口在哪里?题目为什么要强调有一个数字出现一次,其他的出现两次?我们想到了异或运算的性质:任何一个数字异或它自己都等于0。也就是说,如果我们从头到尾依次异或数组中的每一个数字,那么最终的结果刚好是那个只出现一次的数字,因为那些出现两次的数字全部在异或中抵消掉了。

有了上面简单问题的答案之后,我们回到原始的问题。如果能够把原数组分为两个子数组,在每个子数组中,包含一个只出现一次的数字,而其他数字都出现两次,那么按照前面的办法就可以分别求出这两个只出现一次的数字了。

假如这两个数为a和b,那么将所有的数异或得到的数必定为a^b。由于a和b不相等,那么a^b != 0,也就是说在a^b中必定至少有一位为1,对应位上a与b不一样,根据这一位,我们可以将a和b分开,并将数分成两组。注意,两个相同的数肯定会被分到同一个组。    我们在结果数字中找到第一个为1的位的位置,记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组,第一个子数组中每个数字的第N位都为1,而第二个子数组的每个数字的第N位都为0

现在我们已经把原数组分成了两个子数组,每个子数组都包含一个只出现一次的数字,而其他数字都出现了两次。因此到此为止,所有的问题我们都已经解决。

  1. int findNotDouble(int a[], int n)
  2. {
  3.     int result = a[0];
  4.     int i;
  5.     for(i = 1; i < n; ++i)
  6.         result ^= a[i];
  7.     return result;
  8. }

  9. void findOutTwoOdds(int a[], int n, int &odd1, int &odd2)
  10. {
  11.     int x = findNotDouble(a, n);
  12.     int y=1, i;
  13.     // find 'y' to indicate the first bit which is 1 in (a^b)
  14.     for(y = 1; y <= x; y <<= 1)
  15.     {
  16.         if(y & x)
  17.             break;
  18.     }
  19.     // divide the datas into two groups
  20.     for(i = 0; i < n; ++i)
  21.     {
  22.         if(y & a[i])
  23.             odd1 ^= a[i];
  24.         else
  25.             odd2 ^= a[i];
  26.     }
  27. }
  1. int main()
  2. {
  3.     int A[]={4, 5, 3, 4, 5, 7, 7, 6, 8, 8};
  4.     int num = sizeof(A)/sizeof(int);
  5.     int odd1 = 0, odd2 = 0;
  6.     
  7.     findOutTwoOdds(A, num, odd1,odd2);
  8.     printf("the two numbers are %d and %d.\n", odd1, odd2);
  9.     return 0;
  10. }
阅读(2590) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~