问题：您给出从1号的序列至n-1与重复一次的号码之一。 （例如：1 2 3 3 4 5）。你怎么能找到重复的号码？

Problem: you are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). how can you find the repeating number?

很多时候，所谓的智能这个问题的答案是总结起来，找到与预期之差。但是，为什么不只是遍历列表及之前的检查多少？两者都是为O（n）。我失去了一些东西？

Very often the so called "smart" answer to this question is to sum it up and find the difference from the expected sum. But why not just walk through the list and check the number before it? Both are O(n). Am I missing something?

推荐答案

聪明的回答是最好的解决方案时，该列表没有排序，因为它访问的每个元素只有一次，并且使用O（1）额外的空间。如果列表中的是的排序，甚至有一个O（log n）的解决方案：你可以做一个二进制搜索。通过观察中央的元素，你可以看到，如果重复的号码是前或元素之后，继续平分，直到你找到它。

The "smart" answer is the best solution when the list is not sorted, because it visits each element only once and uses O(1) additional space. If the list is sorted, there is even a O(log n) solution: You can do a binary search. By looking at the central element, you can see if the duplicate number is before or after that element and continue bisecting until you found it.

例如：

1 2 2 3 4 5 6

的中心元素是3，但它是在第四位置，所以重复之前一定要它。接下来检查是排在第二位的2，让我们来看看第二位置等之后。

The central element is 3, but it is in the fourth position, so the duplicate must be before it. Next check is the 2 in second position, so we have to look after the second position etc.