剑指offer:数组中只出现一次的数字

阳光穿透心脏的1/2处 2022-04-10 09:17 177阅读 0赞

## 题目描述 ##

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

解题思路:

先将所有数字进行异或, 异或结果=两个只出现一次的数字异或的结果,找到**异或结果中1出现的第一个位置**,根据此位是否为1将数组分为两个组分别进行异或,得到两个数字即为两个单独的数字!

AC C++ Solution:

class Solution {
    public:
        void FindNumsAppearOnce(vector<int> data,int* num1,int* num2) {
            if(data.size() < 2)
                return;
              
            int resultExclusiveOR = 0;
            for(int i = 0; i < data.size(); i++){
                resultExclusiveOR ^= data[i];    //全部异或的结果=两个单独数异或的结果
            }
              
            unsigned int index = FindFirstBitIs1(resultExclusiveOR);//找到异或数中第一位为1的位置
              
            *num1 = *num2 = 0;
            for(int j = 0; j < data.size(); j++){
                if(IsBit1(data[j], index))    //index把数组分为两组,一组的index位为1
                    *num1 ^= data[j];        
                else                        //一组的index位为0
                    *num2 ^= data[j];
            }
      
        }
          
        unsigned int FindFirstBitIs1(int num){
            int indexBit = 0;
            while(((num & 1) == 0) && (indexBit < 8*sizeof(int))){
                num = num >> 1;
                indexBit++;
            }
              
            return indexBit;
        }
          
        bool IsBit1(int num, unsigned int indexBit){
            num = num >> indexBit;
            return (num&1);
        }
          
    };