首页 > 试题广场 >

数组中只出现一次的数字

[编程题]数组中只出现一次的数字
  • 热度指数:450661 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
推荐
class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
  if(data.size()<2)
   return ;
  int size=data.size();
  int temp=data[0];
  for(int i=1;i<size;i++)
   temp=temp^data[i];
  if(temp==0)
   return ;
  int index=0;
  while((temp&1)==0){
   temp=temp>>1;
   ++index;
  }
  *num1=*num2=0;
  for(int i=0;i<size;i++)
  {
   if(IsBit(data[i],index))
    *num1^=data[i];
   else
    *num2^=data[i];
  }
    }
 bool IsBit(int num,int index)
 {
  num=num>>index;
  return (num&1);
 }
};
可以用位运算实现,如果将所有所有数字相异或,则最后的结果肯定是那两个只出现一次的数字异或
 的结果,所以根据异或的结果1所在的最低位,把数字分成两半,每一半里都还有只出现一次的数据和成对出现的数据
 这样继续对每一半相异或则可以分别求出两个只出现一次的数字
编辑于 2015-08-18 23:24:57 回复(77)

问题信息

难度:
0条回答 159340浏览

热门推荐

通过挑战的用户