问题:给出一系列从1到n-1的数字,其中一个数字只重复一次.(例如:1 2 3 3 4 5).你怎么能找到重复的数字？
通常,对这个问题的所谓"聪明"回答是将其总结并找出与预期总和的差异.但为什么不只是走过清单并检查之前的数字呢？两者都是O(n).我错过了什么吗？
Sve*_*ach 23
当列表未排序时,"智能"答案是最佳解决方案,因为它仅访问每个元素一次并使用O(1)额外空间.如果列表已排序,甚至还有一个O(log n)解决方案:您可以进行二进制搜索.通过查看中心元素,您可以查看重复的数字是在该元素之前还是之后,并继续二等分直到找到它为止.
例:
1 2 2 3 4 5 6
中心元素是3,但它处于第四位,因此副本必须在它之前.接下来检查是第二个位置的2,所以我们必须照顾第二个位置等.