找到在O(n)时间O(1)空间中不重复的数字

Question

对于初学者,我确实看过这些问题:

给定一个整数数组,其中一些数字重复1次,一些数字重复2次,只有一个数字重复3次,你怎么找到重复3次的数字

在数组中查找两个重复数字的算法,无需排序

这一个不同:

给出一个带有一个唯一编号的未排序整数数组,其余数字重复3次,即:

  {4,5,3,  5,3,4, 1, 4,3,5 }

我们需要在O(n)时间和O(1)空间中找到这个唯一的数字

注意:这不是一个功课,只是我遇到一个很好的问题

Answer 1

这个如何:

想法:按位添加mod 3

#include <stdio.h>

int main() {
    int a[] = { 1, 9, 9, 556, 556, 9, 556, 87878, 87878, 87878 };
    int n = sizeof(a) / sizeof(int);
    int low = 0, up = 0;

    for(int i = 0; i < n; i++) {
        int x = ~(up & a[i]);
        up &= x;
        x &= a[i];
        up |= (x & low);
        low ^= x;
    }
    printf("single no: %d\n", low);
}