面试题56 - II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：

• 1 <= nums.length <= 10000

• 1 <= nums[i] < 2^31

Solutions

1. bit operations

2. See problem 137 for detailed explanation.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int seen_once = 0, seen_twice = 0;
        for (auto n : nums) {
            seen_once = ~seen_twice & (seen_once ^ n);
            seen_twice = ~seen_once & (seen_twice ^ n);
        }

        return seen_once;
    }
};

Or

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int x2 = 0, x1 = 0;
        for (auto n : nums) {
            x2 ^= x1 & n;
            x1 ^= n;
            int mask = ~(x1 & x2);
            x1 &= mask;
            x2 &= mask;
        }

        return x1;
    }
};