牛客刷题数组之数组中只出现一次的数字

题目描述

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

牛客链接：

https://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811?tpId=13&&tqId=11193&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

代码一：

暴力解决，通过两层循环找到两个数字，时间复杂度为o（n*n）

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int len = data.size();
        if (len < 2) {
            return ;
        }
        vector<int> res;
        for(int i=0; i<len; i++) {
            bool flag = false;
            for(int j=0; j<len; j++) {
                if (data[i] == data[j] && i != j) {
                    flag = true;
                    break;
                }
            }
            if(!flag ) {
                res.push_back(data[i]);
            } 
        }
        *num1 = res[0];
        *num2 = res[1];
        return ;
    }
};

代码二：

用位运算实现，如果将所有所有数字相异或，则最后的结果肯定是那两个只出现一次的数字异或的结果
根据异或的结果1所在的最低位，把数字分成两半，每一半里都还有只出现一次的数据和成对出现的数据
这样继续对每一半相异或则可以分别求出两个只出现一次的数字

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int len = data.size();
        int temp = data[0];
        for(int i=1; i<len; i++) {
            temp = temp^data[i];
        }
        int index = findFirstBit1(temp);
        *num1 = 0;
        *num2 = 0;
        for(int i=0; i<len; i++) {
            if(bitIs1(data[i], index)) {
                *num1 = *num1^data[i];
            } else {
                *num2 = *num2^data[i];
            }
        }
        return ;
    }
    
    int findFirstBit1(int num) {
        int index = 0;
        while((num&1) == 0) {
            num = num>>1;
            index++;
        }
        return index;
    }
    
    bool bitIs1(int num, int index) {
        num = num>>index;
        return num&1;
    }
};

注意：
异或规律