[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如下(參考資料)

	class Solution {
	public:
	int singleNumber(vector<int>& nums) {
	int ans = 0;
	for(int i = 0; i < 32; i++) {
	int sum = 0;
	for(const auto &n : nums) {
	//>> calculate how many times one number show up
	//>> in the form of bit
	sum += (n >> i) & 1;
	}
	ans |= (sum % 3) << i;
	}
	return ans;
	}
	};

view raw singleNumberInArray2_1.cpp hosted with ❤ by GitHub

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

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

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

code如下(參考資料)

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

view raw singleNumberInArray2_2.cpp hosted with ❤ by GitHub

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

想法如下

• 整個狀態的轉換是，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++

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

view raw sumRootToLeafNum2_3.cpp hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun singleNumber(nums: IntArray): Int {
	var one = 0
	var two = 0
	for(n in nums) {
	one = (one xor n) and two.inv()
	two = (two xor n) and one.inv()
	}
	return one
	}
	}

view raw single_number_2.kt hosted with ❤ by GitHub