剑指offer面试题[40]-数组中只出现一次的数字

谁借莪１个温暖的怀抱￠ 2022-06-12 13:59 178阅读 0赞

## 题目描述 ##

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

**注意原题目要求空间复杂度为0(1)。**

**位运算的具体思路可以参看剑指offer。**

class Solution {
    public:
        void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
           //若要求空间复杂度为0(1),时间复杂度为O(n),可以用位运算
           int len=data.size();
           int resultOrElse=0;
           for(int i=0;i<len;i++)
               resultOrElse^=data[i];         //所有数字求抑或
           unsigned int indexOf1=FindFirstBitIs1(resultOrElse);  //找到数字中resultOrEl从右开始对应二进制中第一位为1的位置
            *num1=0;
            *num2=0;
           for(int i=0;i<len;i++)
             {
                 if(IsBit1(data[i],indexOf1))
                     *num1^=data[i];
                 else
                     *num2^=data[i];
             }
        }
          unsigned int FindFirstBitIs1(int m) 
          {
            int index=0; 
            while(((m&1)==0)&&(index<8*sizeof(int)))
              {
                m=m>>1;
                index++;
              }
            return index;
          }
        bool IsBit1(int num,unsigned int n)   //判断num对应二进制中第n位是否为1
          {
             if((num>>1)&1==1)
                 return true;
             else
                 return false;
          }
    };
    
    /*map容器匹配法，空间复杂度O(n).
    class Solution {
    public:
        void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
           map<int,int> m;
           int len=data.size();
           vector<int> vec;
           for(int i=0;i<len;i++)
              m[data[i]]++;
           map<int,int>::iterator iter;  
           for(iter=m.begin();iter!=m.end();iter++)  
           {  
              if(iter->second==1)
                  vec.push_back(iter->first);
              if(vec.size()==2)
                  break;
           }  
           *num1=vec[0];
           *num2=vec[1];
        }
    };
    */