未分類

Single Number II

BitManipulation, Go, LeetCode

Single Number II

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?

提示 解題應用
BitManipulation XOR,AND,NOT

Default:

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

解答思路:

雖然說之前有一篇Single Number，不過這次如果是重覆的資料出現三次而要找出落單的值，在同樣要時間複雜度要O(n)而空間複雜度則是O(1)的情況下，做法與概念跟先前只重覆兩次不同，摸索半天也無法藉由先前題目經驗來啟發，討論區有人提出了非常漂亮的解法，完全符合時間與空間複雜度的條件，主要就是以兩個變數(分為儲存與備份)來對位元的操作結果進行儲存，利用迴圈遍歷陣列取出每個元素來做以下動作(兩個變數save/backup初始值為0;value為元素值):

1
2
save = (save ^ value) &^ backup
backup = (backup ^ value) &^ save

變數與元素做XOR其概念可參考前一篇，XOR能保留對應數量的位元組合，至於為何能將重覆三次的資料篩選掉，連續取出三個相同的值來看的話其流程大致如下:

第一次取出X值，save暫存X值而backup還尚未儲存

1
2
save: X
backup: 0

第二次再取出X值，save清除該值而backup會備份先前的X值

1
2
save: 0
backup: X

第三次仍是取出X值的話，save與backup最後都會彼此清空

1
2
save: 0
backup: 0

透過如此巧妙的篩選方式只要資料是重覆三次甚至更多，要來找出落單的值都能適用於該作法。

程式碼解說:

程式碼相單純並不複雜，詳細的概念可以參考上述解答思路，建議可以自行推演一遍來加速理解

1
2
3
4
5
6
7
var save int
var backup int
for _, v := range nums {
	save = (save ^ v) &^ backup
	backup = (backup ^ v) &^ save
}
return save

完整程式碼:

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

總結:

陣列中重覆的資料會出現三次而要找出唯一落單的值，其作法是每次從陣列取出元素時，做以下的操作(兩個變數save/backup初始值為0;value為元素值):

1
2
save = (save ^ value) &^ backup
backup = (backup ^ value) &^ save

如果連續取出三個相同的值，第一次進來的重覆值會暫存在save中，第二次重覆值進來save會清除該值而backup會備份該值，第三次再進來save與backup都會彼此清除該值，透過此作法來篩選只要資料是重覆三次甚至更多的情況都能用來找出落單的值。

分享到