0268. Missing Number (Easy)

(當然，Medium的拍手也可以多拍幾下啦XD)

Question

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

Example 1

1
2

Input: [3,0,1]
Output: 2

Example 2

1
2

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

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

分析/解題

給定一個陣列內含n個不同的數字，
(從0~n之間選n個，也就是說會少一個)
試找出漏掉的那個數。

首先最笨最暴力的方法當然是排序過後再從0開始看nums[i]是否為i。
這個做法顯然經過排序就需要O(NlogN)的時間，
但其實還是可以通過測資XD

我們考慮比較簡單一點的作法：
我們都知道梯形公式(以及那個聰明的高斯XD)，
從0加到n的總和會是n * (n+1) / 2。

所以想要知道中間漏掉哪個，就將0~n的總和，
減去nums的所有元素全部加起來即可。

Java

在Python中不要忘記了除法取整數要用「//」，
並且陣列的和可以用sum來取得。

Python

這種解法要留意一點，如果在有限制int的狀態下，
n*(n+1)是有機會溢位的！所以如果有時間的話，
還是可以嘗試一下下面提到的解法。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1)，乘法只做一次，加法會做n次，儲存的部分只有幾個輔助的變數)

「這題有別的解法嗎？」
(其實用Bitwise Operation來解也很簡單，
這邊留給讀者可以自行嘗試看看(用XOR)。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~