未分類

Single Number

BitManipulation, Go, HashTable, LeetCode

Single Number

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

Note:

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

提示 解題應用
HashTable Hash Map
BitManipulation XOR

Default:

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

解答思路:

最初看到發現這題也有一對一的關係存在，因為強調有每一組數字，而我們要找的就是那唯一一個落單的數字，也許可以用stack來處理，或者是Hash Map(如果每組數字都不一樣沒有重覆的話)，不過在註記的部分發現到不但要實現O(1)的複雜度，而且也不能用額外的空間，換句話說不需要用到空間換取時間，有更簡單的方式可以完成，在注意到BitManipulation之後，進而才發現XOR也是一個不錯的方式，XOR原理是將兩數字換成2進位之後，1與1的部分歸0，1與0則保留1，0與0則依舊為0，所以說如果是相同的數字做XOR自然就為0，而0與其它數字做XOR就會保留該數字，如下: 

1
2
3
4
A ^ B ^ C ^ B ^ C ^ A ^ N
= A ^ A ^ B ^ B ^ C ^ C ^ N
= 0 ^ 0 ^ 0 ^ N
= N

如此一來就能在不利用額外空間的狀況下達到O(1)的複雜度。

程式碼解說:

看起來似乎沒什麼要提的，只是對整個數字陣列一個個取出做XOR(^)，最後剩下的就是目標

1
2
3
4
5
var result int
for _, v := range nums {
	result ^= v
}
return result

完整程式碼:

1
2
3
4
5
6
7
func singleNumber(nums []int) int {
	var result int
	for _, v := range nums {
		result ^= v
	}
	return result
}

總結:

一對一的關係除了可以用stack或Hash Map(如果每組數字都不一樣沒有重覆的話)來處理，如果是要找唯一一個非對應的結果除了可以用上述的方式來篩選到最後剩下來的之外，對所有的資料做XOR也是一個不錯的選擇，尤其是當每筆資料能單單只轉成數字的時候。

分享到