Leetcode 题解 C++ Single Number I II III

在Leetcode上做了Single Number系列的三道题，都是与位运算有关的，感觉都挺巧妙。

Leetcode 136 Single Number I

题意

一组数中只有一个数字是出现一次的，其他的数字都恰好出现两次，现在求只出现一次的数是多少。

分析

根据异或的性质，答案是所有的数字的异或和。

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        for (int i = 1; i < nums.size(); i++)
            nums[0] ^= nums[i];
        return nums[0];
    }
};

Leetcode 137 Single Number II

题意

一组数中只有一个数字是出现一次的，其他的数字恰好都出现三次，现在求只出现一次的数是多少。

分析

显然，假如还是用上一题的做法，直接将数字异或起来，是得不到答案的。为什么上一题的答案直接异或起来就可以，因为出现两次的数字异或后等于出现零次，具体对于某一位来说，它会经过0->1->0这么个过程。而对于这道题，假如某个数字出现了三次，那么对于具体某一位来说，它会经过0->1->0->1这个过程。因此，我们应用两个位来表示具体某一位的状态变化，即让它经过00->10->01->00这么个过程。

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0;
        int twos = 0;
        for (auto i: nums) {
            ones = (ones ^ i) & ~twos;
            twos = (twos ^ i) & ~ones;
        }
        return ones;
    }
};

Leetcode 260 Single Number III

题意

一组数中只有两个数字是出现一次的，其他的数字恰好都出现两次，现在求只出现一次的数是哪两个。

分析

我们先将所有数字异或起来，得到c。设答案为a和b，那么c = a ^ b。

对于这个c的各个位，有的是0，有的是1。值为1的位，意味着只属于a或b。因此，我们可以任意取c中一个值为1的位，将所有数字划分为两个可重集合，这两个集合的数字分别异或起来就是答案。

代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int sum = 0;
        for (auto i: nums) {
            sum ^= i;
        }
        sum &= -sum;
        vector<int> ans = {0, 0};
        for (auto i: nums) {
            if (sum & i) {
                ans[0] ^= i;
            } else {
                ans[1] ^= i;
            }
        }
        return ans;
    }
};