劍指Offer56-Ⅱ.數組中數字出現的次數Ⅱ

• 題目：劍指Offer56-Ⅱ.數組中數字出現的次數Ⅱ

  輸入一個數組nums，其中隻有一個數出現一次，其餘數均出現3次；

  找到那個出現一次的數；

  1 <= nums.length <= 10000；（說明n ^ 2也可以）

  1 <= nums[i] < 2^31

• 思路：1，2正常思路，3，4好辦法

  1.哈希表：時間O(n)：掃兩次nums，空間O(n)：幾乎每個數都出現3次，是以哈希表隻需要存n/3的數即可；

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int x : nums) ++count[x];//第一次周遊存下每個數出現的次數

        for (int x : nums) 
            if (count[x] == 1) return x;//第二次周遊，找到那個隻出現一次的數

        return -1;//如果一定有隻出現一次的數的話，是走不到這裡的
    }
};
           

3.sort：時間O(nlogn)，空間O(logn)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 1; ) {
            if (nums[i] == nums[i + 1]) i += 3;//跳過這3個相同數字
            else return nums[i];//否則說明找到了
        }
        
        return nums[n - 1];//走到這說明目标數字在結尾，被跳過了
    }
};
           

3.逐位周遊：時間O(n)，空間O(1)：額外需要一個大小為32的數組；

例如3，3，3，4，其中3出現3次，4出現1次

0 1 1 = 3
0 1 1 = 3
0 1 1 = 3
1 0 0 = 4
-----
1 3 3
%3
1 0 0 = 4
           

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int count[32] = {0};//個位，十位，百位。。。，int共32位
        for (int x : nums) {//第一次掃，統計這些數字每位為1的個數;根據局部性原理，每個數統計完再下個數，比先統計每個數的第0位再統計每個數的第1位要好
            //盡管這裡m一定是>1的，左移是邏輯左移，但lc認為有符号數的左移是未定義的，是以這裡需要定義為unsigned
            for (int i = 0, unsigned int m = 1; i < 32; ++i, m <<= 1) {
                if (x & m) count[i]++;//這種寫法x不動，不斷右移m,去&x
            }
            /*
            for (int i = 0; i < 32; ++i) {
            	count[i] += (x & 1);
            	x >> 1;//這種寫法不斷>>，去&1更直覺，但要注意，為了防止改變數組中的x，外層for循環不能寫for(int& x : nums)
			}
			*/
        }
    
        int res = 0;
        for (int i = 31; i >= 0; --i) {//第二次掃，對每位%3,無論出現次數為3的數字在該為是0還是1，%3就把它們都去掉了，隻剩下出現次數為1的目标數的該位
            res  = (res << 1) + (count[i] % 3);//類似于十進制，從高位往低位讀，例如234，0*10+2=2，2*10+3=23，23*10+4=234
        } 
        
        return res;
    }
};
           

4.（最優解）有限狀态自動機：

人都傻了，看不懂

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0;
        int two = 0;
        for(auto n:nums){
            one = (one^n) & ~two;
            two = (two^n) & ~one;
        }
        return one;
    }
};
           

• 總結：

  有限狀态機不會用啊！！