爲什麼我必須總結才能找到重複的號碼？

Question

問題：給出一個從1到n-1的數字序列，其中一個數字只重複一次。 （例如：1 2 3 3 4 5）。你怎麼能找到重複的號碼？

很多時候，這個問題的所謂「聰明」答案是總結並找出預期總和的差異。但爲什麼不直接瀏覽清單並檢查之前的數字？兩者都是O（n）。我錯過了什麼嗎？

Answer 1

當列表沒有排序時，「智能」答案是最好的解決方案，因爲它只訪問一次元素並使用O（1）個額外空間。如果列表是排序，那麼甚至有一個O（log n）解決方案：您可以執行二分搜索。通過查看中心元素，您可以看到重複數字是在該元素之前還是之後，並繼續平分直到找到它。

實施例：

1 2 2 3 4 5 6 

中心元件是3，但它是在第四位置，所以重複的必須是之前它。接下來檢查是排在第二位的2，所以我們必須在第二位置後看等

Answer 2

如果數字排序，那麼你不會錯過任何東西。

Answer 3

要知道misterious數x你只需要在序列中總結所有號碼：

S = sum(sequence) 
S = sum(from 1 to (n - 1)) + x 

sum(from A to B) = 1/2 * (A + B) * (B - A + 1) 

sum(from 1 to (n - 1)) = 1/2 * (1 + (n - 1)) * ((n - 1) - 1 + 1) = 1/2 * n * (n - 1) 

x = S - sum(from 1 to (n - 1)) 

x = S - 1/2 * n * (n - 1)