问题：给你一个从 1 到 n-1 的数字序列，其中一个数字仅重复一次。 （例如：1 2 3 3 4 5）。如何找到重复的数字？
通常，这个问题的所谓“聪明”答案就是将其总结并找出与预期总和的差异。但为什么不直接浏览列表并检查前面的数字呢？两者都是 O(n)。我错过了什么吗？
当列表未排序时，“智能”答案是最佳解决方案，因为它仅访问每个元素一次并使用 O(1) 额外空间。如果列表is排序后，甚至有一个 O(log n) 解决方案：您可以进行二分搜索。通过查看中心元素，您可以查看重复的数字是在该元素之前还是之后，并继续平分直到找到它。
Example:
1 2 2 3 4 5 6
中心元素是 3，但它位于第四个位置，因此重复项必须在它之前。下一个检查是第二个位置的 2，所以我们必须照顾第二个位置等。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
