LeetCode之Single Number II

【题目】

Given an array of integers, every element appearsthreetimes 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：创建一个长度为 sizeof(int) 的数组 count[sizeof(int)]，count[i] 表示所有元素的 1 在 i 位出现的次数。

如果 count[i] 是 3 的整数倍，则忽略；否则就把该位取出来组成答案。
方法 2：用 ones 记录到当前处理的元素为止，二进制 1 出现“1 次”（mod 3 之后的 1）的有哪些二进制位；

用 twos 记录到当前计算的变量为止，二进制 1 出现“2 次”（mod 3 之后的 2）的有哪些二进制位。

当 ones 和 twos 中的某一位同时为 1 时表示该二进制位上 1 出现了 3 次，此时需要清零。

即用二进制模拟三进制运算。最终 ones 记录的是最终结果。

【代码1】

/*********************************
*   日期：2014-01-26
*   作者：SJF0115
*   题号: Single Number II
*   来源：http://oj.leetcode.com/problems/single-number-ii/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

class Solution {
public:
    int singleNumber(int A[], int n) {
        int i,j;
        //整数字长
        int w = sizeof(int) * 8;
        int result = 0;
        //count[i]表示所有数字在二进制表示中1在第i位上的次数
        int count[w];
        //初始为0
        for(i = 0;i < w;i++){
            count[i] = 0;
        }
        for(i = 0;i < n;i++){
            for(j = 0;j < w;j++){
                //二进制中第j位
                count[j] += (A[i]>>j) & 1;
                //count[j]是3的倍数，这是由那些出现3次数字产生的则置为0
                count[j] %= 3;
            }//for
        }//for
        for(i = 0;i < w;i++){
            //printf("%d ",count[i]);
            result += (count[i] << i);
        }
        return result;
    }
};
int main() {
    Solution solution;
    int result;
    int A[] = {2,2,2,6,4,4,4};
    result = solution.singleNumber(A,7);
    printf("Result:%d\n",result);
    return 0;
}

【代码2】

class Solution {
public:
    int singleNumber(int A[], int n) {
        int ones = 0, twos = 0, threes = 0;
        for (int i = 0; i < n; ++i) {
            twos |= (ones & A[i]);
            ones ^= A[i];
            threes = ~(ones & twos);
            ones &= threes;
            twos &= threes;
        }
        return ones;
    }
};