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

Answer 2

此解决方案适用于所有输入。想法是从数组中提取整数的位并添加到相应的 32 位位图“b”（实现为 32 字节数组以表示 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);
}