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

题目描述

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

解题思路

异或大法好，如果一个数组只有1个数字出现一次，其他数字都出现偶数次，那么异或这个数组的结果就是那个数字（相同为0，相同的数字会抵消）。如果这个数组中有两个数字只出现了一次，那么就需要划分子数组，使得每个子数组中只包含一个只出现一次的数字。划分的关键就是异或结果1的位置，因为异或的结果就是那两个只出现一次的数字异或的结果，而结果中的1正好能分开这两个数字，这两个数字1的位置处肯定是不同的所以才会出现1。于是，根据划分关键对数组进行划分，然后对每个子数组求异或结果就是那两个数。

Code

class Solution {
public:
    
    int Get1Index(int input) {
        int flag = 1, index = 0;
        while(index < 32) {
            if(flag & input) {
                return index;
            }
            flag = flag << 1;
            index++;
        }
        return index;
    }
    int GetXorOfArray(vector<int> data) {
        int result = data[0];
        for(int i = 1; i<data.size(); i++) {
            result ^= data[i];
        }
        return result;
    }
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.size() < 2) return;
        int result = GetXorOfArray(data);
        int index = Get1Index(result);
        int flag = 1 << index;
        vector<int> data1, data2;
        for(int i = 0; i<data.size(); i++) {
            if(flag & data[i]) {
                data1.push_back(data[i]);
            } else {
                data2.push_back(data[i]);
            }
        }
        *num1 = GetXorOfArray(data1);
        *num2 = GetXorOfArray(data2);
    }
};

总结

评论区关于求关键的方法犹如神仙打架，膜各位计组大佬

	int n1=(((~x)+1)&x);//~x+1使最低位的1不变，再其位之上的变为相反  x的最低位1以下是全是0   &这样得000010000