剑指56：数组中数字出现的次数

传送门

nowcoder
leetcode

题目描述

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

C++ 代码 - nowcoder

/*
    异或
    n = n & (-n)：取出 n 表示二进制最低位的 1
*/
class Solution {
public:
    void FindNumsAppearOnce(vector<int> nums, int* num1,int *num2) {
        if (nums.size() < 2) return;

        int diff = 0;
        for (int x : nums) {
            diff ^= x;
        }
        diff = diff & (-diff); // 标志位，记录 diff 中第一个 1 的位置
        
        num1[0] = 0, num2[0] = 0;
        for (int x : nums) {
            if ((x & diff) == 0) {
                num1[0] ^= x;
            } else {
                num2[0] ^= x;
            }
        }
    }
};

C++ 代码 - leetcode

/*
    异或
    n = n & (-n)：取出 n 表示二进制最低位的 1
*/
class Solution {
public:
    vector<int> sockCollocation(vector<int>& nums) {
        if (nums.size() < 2) return vector<int>();

        int diff = 0;
        for (int i = 0; i < nums.size(); i ++) {
            diff ^= nums[i];
        }
        // diff = diff & (-diff); // 标志位，记录 diff 中的第一个 1 的位置
        int lowbit = 1;
        while ((lowbit & diff) == 0) lowbit <<= 1;

        int num1 = 0, num2 = 0;
        for (int x : nums) {
            if ((x & lowbit) == 0) {
                num1 ^= x; // 标志位为 0
            } else {
                num2 ^= x; // 标志位为 1
            }
        }

        return vector<int>{ num1, num2 };
    }
};