首页 > ACM题库 > LeetCode > LeetCode-Single Number II[数组]
2014
11-19

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?

标签: Bit Manipulation
分析

本题和上一题 Single Number,考察的是位运算。

方法1:创建一个长度为{sizeof(int)}的数组{count[sizeof(int)]},{count[i]}表示在在$i$位出现的1的次数。如果{count[i]}是3的整数倍,则忽略;否则就把该位取出来组成答案。

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

代码1

// 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

// 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;
    }
};

相关题目

Single Number


  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  4. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。