leetcode_137

发表于   |   分类于

Single Number II

题目戳这

题意

给定一个数组，数组中只有一个数字只出现了一次，其他数字都出现了3次，求出现一次的那个数字。

解法

看到两种解法。。

第一种解法代码长一些，但是好理解。数字都是在32位之内的，那么我们就用一个32位的数组来存储每个位置上二进制中1的个数。然后对每个位置上1的数目都对对3取余，如果某个数字出现了3次，那么这个位置上1的个数肯定是3的倍数，这样就被化为0了，否则的话取余结果就为1，然后用位运算将二进制化为十进制即可得到只出现一次的那个数字。

第二种解法说实话不太好理解，说是用的两位数字来对应存储某个数字出现了多少次，循环是00-10-01-00，实际上用的是类似三进制，如果出现一次状态就为10，出现两次状态为01，出现三次状态变回为00。具体的话可以用代码模拟几遍，是这样子的。至于推导的话，据说用到了真值表，，但是不太懂。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int bits[32] = {0};
        int res = 0;
        for(int i=0;i<32;i++){
            for(int j=0;j<nums.size();j++){
                bits[i] += (nums[j]>>i)&1;
            }
            res |= (bits[i]%3)<<i;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
}