题目如下
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?

问题:给一个数组,里面只有一个数字一次,其它数字都出现3次,找出这个出现一次的数字,要求时间复杂度为O(n),空间复杂度为O(1)。

解题思路:

这里我们需要用到的知识为二进制、位计算。这里需要思考数字在计算机是怎么存储的。考虑全部用二进制表示,如果我们把第i个位置上所有数字的和对3取余,那么只会有两个结果 0 或 1 (根据题意,3个0或3个1相加余数都为0).

AC代码如下:

#include <stdio.h>
int singleNumber(int A[], int n) {
    int count[32] = {0};
    int result = 0;
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < n; j++) {
            //判断A[J]的第i位的奇偶,奇数才加,偶数为0不加
            if ((A[j] >> i) & 1) {
                count[i]++;
            }
        }
        // 计算第i位的和,然后计算其对应的10进制,再通过与运算求和(其实加法求和也可以)
        result |= ((count[i] % 3) << i);
    }
    return result;
}

我们可以用一组CASE来测试一下 {12, 1, 12, 3, 12, 1, 1,15, 3, 3}

最后依次统计各位上的和如下

qq20150515-1@2x.png - 大小: 12 KB - 尺寸: 168 x 423 - 点击打开新窗口浏览全图

依次为 4447,高位为0直接省略。最后求余之后为 为 1111,转换为2进制则为 8+4+2+1 = 15

算法中值得注意的是:

通过位运算 (A[j] >> i) & 1 来判断奇偶

因为此题又看了一下位运算,感觉CS的世界博大精深