未分類

Single Number III

BitManipulation, Go, LeetCode

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
提示 解題應用
BitManipulation XOR,AND

Default:

1
2
3
func singleNumber(nums []int) []int {
}

解答思路:

先前有一篇Single Number，對所有的資料做XOR以找出唯一一個落單的數字，更多細節可以參考該篇，總之這次我們也使用相同的方式，不過因為落單的會有兩個元素，出來的結果是兩個落單元素做XOR，由於兩個元素必定不相同(相同的值都透過XOR歸0了)，因此在做XOR時兩兩相同bit為”1”的位置會歸0，其餘bit為”1”的位置則會保留，如下:

1
2
3
4
1111   15
0101    5
----  XOR
1010   10

至於要如何從這個值之中找出唯二落單的值，被保留下來的bit為”1”的部分成了我們重要的線索，因為每個1分別代表兩個值各自不同的部分，所以接下來只要從中隨意抽出一個1的位置作為依據，便可以將兩個落單的值給區隔開來，這邊我們是將XOR後的結果與其負數做AND(&)便可得到最右邊bit的”1”，如下:

1
2
3
4
0...0001010   10
1...1110110  -10
-----------  AND
       0010    2

接下來就可以再次遍歷整個數列，並將每個取出的值與上述依據做AND，如果結果為0(該數不包含此依據)便分作一堆，結果不為0則分作另一堆，最後我們就可以將數列拆成兩堆，且兩個落單的值分別落在其中一堆(其餘兩個相同的值勢必會在同一堆)，此時再各別做XOR就可以篩出兩個落單元素了。

程式碼解說:

一開始先初始化要用來存放兩個落單元素的結果陣列，接下來就利用迴圈從數列取出元素，並對所有的資料做XOR，而如思路所述從中抽出最右邊位置bit的”1”作為依據(將XOR後的結果與其負數做AND)，最後再次遍歷整個數列，並將每個取出的值與上述依據做AND，如果結果為0(該數不包含此依據)分作一堆(結果陣列第一個位置)，結果不為0則分作另一堆(結果陣列第二個位置)，此時再各別做XOR就可以篩出兩個落單元素了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var tmp int
result := make([]int, 2)
for _, v := range nums {
	tmp ^= v
}
tmp &= -tmp
for _, v := range nums {
	if v&tmp == 0 {
		result[0] ^= v
	} else {
		result[1] ^= v
	}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func singleNumber(nums []int) []int {
	var tmp int
	result := make([]int, 2)
	for _, v := range nums {
		tmp ^= v
	}
	tmp &= -tmp
	for _, v := range nums {
		if v&tmp == 0 {
			result[0] ^= v
		} else {
			result[1] ^= v
		}
	}
	return result
}

總結:

陣列中重覆的資料會出現二次而要找出唯二落單的值，可以先參考Single Number，其做法為對所有的資料做XOR，不過因為落單的會有兩個元素，出來的結果是兩個落單元素做XOR(兩兩相同bit為”1”的位置會歸0，其餘bit為”1”的位置則會保留)，被保留下來的bit為”1”的部分成了我們重要的線索，因為每個1分別代表兩個值各自不同的部分，所以接下來只要從中隨意抽出一個1的位置作為依據(例如:將XOR後的結果與其負數做AND便可得到最右邊bit的”1”)，便可以將兩個落單的值給區隔開來，最後再次遍歷整個數列，並將每個取出的值與上述依據做AND，如果結果為0(該數不包含此依據)分作一堆，結果不為0則分作另一堆，而兩個落單的值分別落在其中一堆(其餘兩個相同的值勢必會在同一堆)，此時再各別做XOR就可以篩出兩個落單元素了。

分享到