題目連結: Missing Number

題目描述為給定一個長度為 n 的陣列，裡面的元素為從 0,1,2,..,n 中挑選，元素彼此相異。要我們找出沒被挑選到的數字為何。

例子 1: input: [3,0,1] output=2
例子 2: input: [9,6,4,2,3,5,7,0,1] output=8

思路 1: Hash法

我們可以建立一組 map 來對應元素是否在陣列中。之後再檢查所有數字，當該數字在表中查不到，該數字即為所求。

• 複雜度評估
  當陣列長度為 N 時，建立 map 需要遍歷整個陣列，檢查數字是否存在也需要遍歷整個陣列，時間複雜度為 O(N)。此方法另外建立了一組 map ，空間複雜度為 O(N)。

參考程式碼

  func missingNumber(nums []int) int {
    m := make(map[int]bool)
    for _,v := range nums {
        m[v] = true
    }
    
    
    for i:=0;i<len(nums);i++{
        if m[i]==false{
            return i
        }
    }
        
    return len(nums)
}

思路 2: 累加法

我們可以先算出 $S_n = 0 + 1 + 2 + \dots + n$ 的數值為何，並減去陣列中所有元素的和，就是所求的數。

• 複雜度評估
  當陣列長度為 N 時，計算陣列中所有元素的和需要遍歷整個陣列，時間複雜度為 O(N)。
  此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

 func missingNumber(nums []int) int {
    sum:=0
    sum=((len(nums)+1)*len(nums))/2

    for _,v:=range nums{
        sum-=v
    }
    
    return sum
}

思路 3: Bit Operation

當我們將 0~n 之間所有數進行 XOR 運算，再與陣列中所有元素進行 XOR 運算，則在陣列中的數字都會被 XOR 運算兩次抵銷掉，而最後剩下的數字即為所求。詳見 Go - Bitwise Operators。而要將 0~n 做 XOR 的步驟，因為在遍歷陣列時，遇到的 index 會是從 0~(n-1)，可以順便對 index 進行 XOR 運算，最後再與 n 做 XOR 運算即完成。

• 複雜度評估
  當陣列長度為 N 時，進行 XOR 運算需要遍歷整個陣列，時間複雜度為 O(N)。
  此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func missingNumber(nums []int) int {
	ans := 0
    ans ^=len(nums)

	for i, v := range nums {
		ans ^= i ^ v
	}

	return ans
}

思路 4: 二分搜尋法

我們也可以先對陣列進行排序，之後比較陣列中的數字與 index ，如果不一致則表示 index 的數字為丟失的數字。

• 複雜度評估
  當陣列長度為 N 時，對陣列排序複雜度為 O(NlogN) ，二分搜尋法複雜度為 O(logN)，結合起來時間複雜度為 O(NlogN)。
  此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func missingNumber(nums []int) int {
	sort.Ints(nums)
    
    head:=0
    tail:=len(nums)
    mid:=0
    
    for head<tail{
        mid=head+(tail-head)/2
        
        if nums[mid]>mid{
            tail=mid
        }else{
            head=mid+1
        }
    }
    
    return tail
}

小結

若題目改為兩個數以上不挑選時，我們只需要修改解法 1 即可。
解法 2 中要對 0~n 加總時，可以仿照解法 3 的方式，在遍歷陣列時將 index 相加。
解法 3 Bit operation 在處理數字相關問題時是很好的工具。
若此題是已排序過則解法 4 二元搜尋法時間複雜度為 O(logN)，為最高效解。

我將解法 1~4 加上簡單的測試，上傳程式碼到此。