给定一个包含 n + 1个整数的数组 nums，其数字都在1到n之间（包括1和n），可知至少存在一个重复的整数。
假设nums只有一个重复的整数，找出这个重复的数。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
示例 3：
输入：nums = [1,1]
输出：1
示例 4：
输入：nums = [1,1,2]
输出：1
提示：
2 <= n <= 3 * 104
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1、二分查找
target表示重复数的值，c[i]，表示nums中，nums[i]的出现次数，可证明：当i < target时，c[i] < i，当i >= target时，c[i] > i，即c[i]为单调递增，可用二分法找到target。
时间复杂度=O(nlogn)，空间复杂度O(1)
思路2：快慢下标（指针）法
利用定理：当快慢下标相等时，快下标再走N步抵达重复数字所在的下标，则从数组0下标开始逐一往后遍历，N次遍历后nums[N]为重复数字
若有收获，就点个赞吧
0 人点赞
