LeetCode--Single Number II in Java

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

這種題目大概第一想法會想用Hashmap
然後Linear Time去做應該是沒問題，不過很明顯不是最好的做法使用的Hashmap空間也會因為給的測資越來越長而變大所以這種題目大部分都會使用到 bitmask的方式來做

考慮全部用binary表示，
如果我們把 第 i個位置上所有數字的和對3取餘，
那麼只會有兩個結果 0 或 1 (因為3個0或3個1相加餘數都為0).
因此取餘數的結果就是那個  Single Number.

public int singleNumber(int[] nums) {
        
    int[] arr=new int[32]; //把每個數字的32位元都一一存下來
    int result = 0;  
    
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < nums.length; j++) {
            if (((nums[j] >> i) & 1)==1) { //把每位元加總起來
                arr[i]++;
            }
         } 
        result |= ((arr[i] % 3) << i);  
        //然後把結果%3之後把結果shift到result
    }
    
    
    return result;

這方法很簡單明瞭，跑起來也不差。

在O(n)之內 但還有不需要空間且更快一點的辦法

則是要用到bit manipulation mask的東西 (這一系列要快都必須這樣做)

在這裡使用三個常數來做

1.ones= 來表示第i-th的bit已經出現1次
2.twos=來表示第i-th的bit已經出現2次
3.threes=來表示第i-th的bit已經出現三次
當three出現的時候就去清除 ones跟 twos最後迴圈完的結果 ones就是本題要的答案

public int singleNumber(int[] nums) {
        
int ones = 0, twos = 0, threes = 0; 

for (int i = 0; i < n; i++) { 

  twos |= ones & A[i]; //twos holds the number appear twice
  ones ^= A[i];  // appear once
  threes = ones & twos; // appear three times
  ones &= ~threes; 
  twos &= ~threes;  
  //這裡會把出現三次的部分 1轉成零　清除ones twos中的threes部分
  return ones;
}

有更厲害的人討論出General solution

推廣到K次以上