[LeetCode] 137. Single Number II

轉自LeetCode

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

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

<Solution>
這題是 Single Number 的衍生題

先看一種解法

• 對於每個出現在 vector 裡面的數，去計算它的出現次數

• 記算方式是使用 bit operation。將每個 int 視為 32bits，當一個數出現三次時，某個bit的位置也會出現三次1，相加起來再和3求餘數，如果不為0，就是要找的數字

code如下(參考資料)

用同樣的概念，來優化一下寫法

• 用三個變數來代表一個數字出現的次數，分別是出現一次、兩次和三次

• 當一個數字出現三次後，要把出現一次和兩次的變數歸零

code如下(參考資料)

上面的解法還可以進一步簡化

想法如下

• 整個狀態的轉換是，0 -> 1 -> 2 -> 0，其實就是 mod 3 會出現的三種狀態

• 要表示三種狀態，總共需要兩個 bits，其狀態轉換如下

00 -> 01，等同於 0 + 1 = 1

01 -> 10，等同於 1 + 1 = 2

10 -> 00 ，等同於 2 + 1 = 0

• 由上面的狀態轉換來推導公式，用兩個變數 one 和 two，分別代表該 bit 出現一次和兩次，也是用來表示狀態轉換的兩個 bits

• 如果number出現次數不到兩次(two = 0)，那麼 one 的狀態轉換就等同於 one ^= number；如果number已經出現兩次了(two = 1)，那麼 one下個狀態就是歸零，所以最後的公式為 one = (one ^ number) & ~two

• 記算完 one 之後，再計算 two(切記)。當number出現一次(one = 1)，two 一定是 0，也就是 two &= ~one；當 number 出現兩次以上(one = 0)，two ^= number，最後的公式就是 two = (two ^ number) & ~one

two  one -> two  one 

 0    0  ->  0    1

 0    1  ->  1    0

 1    0  ->  0    0

code 如下(參考資料)

c++


Kotlin