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

Question

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

Given an array of integers where some numbers repeat 1 time, some numbers repeat 2 times and only one number repeats 3 times, how do you find the number that repeat 3 times

Algorithm to find two repeated numbers in an array, without sorting

这一个不同:

给定一个未排序的整数数组，其中有一个唯一数字，其余数字重复 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);
}