發現許多不爲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

怎麼來到這個一個有趣的問題之一：

理念：做按位加法模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); 
}