LeetCode-Single Number II-位运算

LeetCode-Single Number II----位运算

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

分析理解：

方法1：创建一个长度为int类型的位的个数的数组，也就是 sizeof( int ) * 8。用来一个数的各个位的1的个数，我们知道一个数出现3次，那么这个地方的位的1的个数肯定能整除3，这样就能找出只出现一次的那个数了。

// LeetCode, Single Number II
// 方法1，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    int singleNumber(int A[], int n) {
        const int W = sizeof(int) * 8; // 一个整数的bit数，即整数字长
        int count[W];  // count[i]表示在在i位出现的1的次数
        fill_n(&count[0], W, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < W; j++) {
                count[j] += (A[i] >> j) & 1;
                count[j] %= 3;
            }
        }
        int result = 0;
        for (int i = 0; i < W; i++) {
            result += (count[i] << i);
        }
        return result;
    }
};

方法2：用{one}记录到当前处理的元素为止，二进制1出现“1次”（mod 3 之后的 1）的有哪些二进制位；用{two}记录到当前计算的变量为止，二进制1出现“2次”（mod 3 之后的 2）的有哪些二进制位。当{one}和{two}中的某一位同时为1时表示该二进制位上1出现了3次，此时需要清零。即\textbf{用二进制模拟三进制运算}。最终{one}记录的是最终结果。

// LeetCode, Single Number II
// 方法2，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    int singleNumber(int A[], int n) {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < n; ++i) {
            two |= (one & A[i]);
            one ^= A[i];
            three = ~(one & two);
            one &= three;
            two &= three;
        }

        return one;
    }
};

LeetCode-Single Number II-位运算

Single Number II

相关推荐