未分類

Missing Number

Array, BitManipulation, Go, LeetCode, Math

Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example:

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

Note:

Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

提示 解題應用
Math 規律觀查
BitManipulation XOR

Default:

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

解答思路:

只要能善用與先前類似的概念Single Number，成對的情況下可以很容易的找出少了哪一個值，便可以在線性的複雜度上達到目地，而剛好我們可以知道0~n的所有值，所以可以很容易的產生出完整的另一對，最後只要同時XOR原本陣列的值與另一對完整的值，剩下的值就會是我們的結果，不過要注意有兩個例外，一個是0的值會找不出來所有需要在一邊將值取出陣列時，一邊確定是否為0，另一個則是中間根本沒少值，最後要回傳的是第n的值。

程式碼解說:

由於需要同時XOR陣列的值與0~n的值，剛好我們可以利用取出陣列元素值的同時，連同index值一起做XOR，不過因為陣列中有缺少一個元素，所以再取完值的同時還要再XOR陣列的長度(剛好為n值)，而因為0的值會找不出來，所以在迴圈取值時還需判斷是否有0存在，沒有則直接回傳0，如果0存在而且miss的結果剛好也是0，這時表示0~n-1中間完全沒有少值，便回傳n也就是陣列的長度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var miss int
var exist0 bool
size := len(nums)
for i, v := range nums {
	if v == 0 {
		exist0 = true
	}
	miss ^= v ^ i
}
miss ^= size
if !exist0 {
	return 0
} else if miss == 0 {
	return size
}
return miss

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func missingNumber(nums []int) int {
	var miss int
	var exist0 bool
	size := len(nums)
	for i, v := range nums {
		if v == 0 {
			exist0 = true
		}
		miss ^= v ^ i
	}
	miss ^= size
	if !exist0 {
		return 0
	} else if miss == 0 {
		return size
	}
	return miss
}

總結:

要找出0~n中缺了哪個值，善用XOR成對為0的概念，同時XOR所有陣列中的值與完整的0~n，剩下的值就會是我們的結果，萬一缺的是0或是n則需要另外再做確認。

分享到