なぜ繰り返し番号を見つけるために合計しなければならないのですか？

Question

問題：1からn-1までの数字のシーケンスが与えられ、そのうちの1つだけが1回だけ繰り返されます。 （例：1 2 3 3 4 5）。どのように繰り返し番号を見つけることができますか？

この質問に対するいわゆる「スマートな」答えは、それを合計して予想される合計との違いを見つけることです。しかし、リストの中を歩いてその前の番号を調べるだけではどうですか？どちらもO（n）です。何か不足していますか？

Answer 1

リストがソートされていない場合、「スマート」回答は、各要素を1回だけ訪問し、O（1）の追加スペースを使用するため、最適なソリューションです。リストがにソートされている場合、O（log n）解もあります。バイナリ検索ができます。中央の要素を見ることで、その要素の前後に重複した番号があるかどうかを確認し、見つかるまで二等分することができます。

例：

1 2 2 3 4 5 6 

中心的な要素は3であるが、第4の位置にあるので、重複はその前でなければなりません。次のチェックは、第2の位置にある2であるので、私たちは第二の位置の世話をしなければならないなど

Answer 2

数字がソートされている場合は、何も見当たりません。

Answer 3

あなたが唯一の順序ですべての数字を合計する必要がミステリアス数x知るために：DUP

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)