题解 | #合并两个有序的数组#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型vector
     * @return int整型vector
     */
    int xorRes(vector<int>& array) { // 寻找数组中只出现一次的数字（一轮xor只能找出一个）
        int sum = array[0];
        for (int i = 1; i < array.size(); i++) {
            sum = array[i] ^ sum;
        }
        return sum;
    }
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        int sum = xorRes(array);
        int cnt = 0; // 计算二进制中两个只出现一次的数字的差异位置
                    // 如4（100）和6（110），则在第二个二进制位有差异（xor异为1同为0）
        while (sum % 2 == 0) {
            sum /= 2;
            cnt++;
        }
        vector<int> arr1;
        vector<int> arr2;
        vector<int> res;
        for (int i = 0; i < array.size(); i++) {
            if ((array[i] >> cnt)%2 == 0) // 右移至差异位，则差异位为1的元素为一类，为0的元素为另一类，
                                        //两类分别调用xorRes即得到两个只出现一次的数字
                arr1.push_back(array[i]);
            else
                arr2.push_back(array[i]);
        }
        int a = xorRes(arr1), b = xorRes(arr2);
        if(a > b)
            swap(a, b);
        res.push_back(a);
        res.push_back(b);
        return res;
    }
};