找到在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);
}

Answer 2

此解决方案适用于所有输入。想法是从数组中提取整数的位并添加到相应的32位位图'b'（实现为32byte数组以表示32位数。）

unsigned int a[7] = {5,5,4,10,4,9,9};
unsigned int b[32] = {0};  //Start with zeros for a 32bit no.
main1() {
    int i, j;
    unsigned int bit, sum =0 ;
    for (i=0;i<7; i++) {
        for (j=0; j<32; j++) { //This loop can be optimized!!!!
            bit = ((a[i] & (0x01<<j))>>j); //extract the bit and move to right place
            b[j] += bit; //add to the bitmap array
        }
    }
    for (j=0; j<32; j++) {
        b[j] %= 2;     //No. repeating exactly 2 times.
        if (b[j] == 1) {
            sum += (unsigned int) pow(2, j); //sum all the digits left as 1 to get no
            //printf("no. is %d", sum);
        }
    }
    printf("no. is %d", sum);
}