描述

在一个整型数组中，只有一个元素出现了一次，其他元素出现了一次，找到只出现一次的元素。

要求：时间复杂度为线性的，使用常量的辅助空间。

分析

借助于位运算，创建一个长度为 sizeof(int) 的数组 count[sizeof(int)]，count[i] 表示在在 i 位 出现的 1 的次数。如果 count[i] 是 3 的整数倍，则忽略;否则就把该位取出来组成答案。

实现

// Single Number in threes
int singleNumberInThrees(int a[], int len)
{
    const int w = sizeof(int) * 8;
    int count[w];
    
    fill_n(&count[0], w, 0);
    for(int i=0; i<len; 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;
}