【Leetcode】287.寻找重复数
287 寻找重复数
题目:
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
思路:二分查找
这种方法只和数组中存在哪些数有关,和数组中这些数的顺序无关。因此分析时可把数组看成有序的(但其实并没有对数组进行排序,只是这么分析而已)
数组中所有的数字都在1到n之间,我们先取1到n的中位数mid。统计数组中小于等于mid的元素个数count,如果count大于mid,则说明重复数存在于1到mid之间。否则,重复数存在于mid+1到n之间。
代码:
1 |
|
时间复杂度:O(nlogn)
空间复杂度:O(1)
注:如果没有不能修改数组和空间复杂度的要求,可以采用排序数组和哈希表的方法