Leetcode:signal_number_ii

Leetcode:signal_number_ii

一、 題目

給一個數組，其中只有一個數出現一次，其他的數都出現3次，請找出這個數。要求時間復雜度是O(n)，空間復雜度O(1)。

二、 分析

第一次遇見這樣的題，真心沒思路….前面的signal number中我們可以直接異或得到結果，很顯然這個更復雜了。暴力解法或排序顯然無法滿足時空要求，所以還得回到位運算上，既然是同樣的數出現了三次，我們可以想到他們的二進制表達對應的位置上相同。對於除出現一次之外的所有的整數，其二進制表示中每一位1出現的次數是3的整數倍，將所有這些1清零，剩下的就是最終的數。如果我們在每一個位置上取到出現1的次數，並進行余3操作，則可消除該數。

例如:A[]={2,3,4,3,2,2,3}

0010

0011

0100

0011

0010

0010

0011

= -0-1-6-3-(1的個數)

0100

int型數據為32位，可以開一個大小為32的int型數組存儲N個元素的各個二進制位的1出現的次數，然後將該次數模3運算。

PS:後面幾種方法剛開始真心沒看懂….自己弱菜

class Solution {
public:
    int singleNumber(int A[], int n) {
        int bitint[32]={0};
        int ans=0;
        for(int i=0; i<32; i++){
            for(int j=0; j>i)&1;
            }
            ans|=(bitint[i]%3)<