【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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findDuplicate(int[] nums) {
int n = nums.length - 1;
int left = 1;
int right = n;
while(left < right){
int mid = left + (right - left)/2;
//统计数组中小于等于mid的个数,mid为从1到n的中位数
int count = 0;
for(int num:nums){
if(num <= mid)
count++;
}
//如果小于等于mid的个数大于mid,则说明在1到mid中存在重复元素,否则,在mid+1到n中存在重复元素
if(count > mid)
right = mid;
else
left = mid + 1;

}
return left;
}

时间复杂度:O(nlogn)
空间复杂度:O(1)

注:如果没有不能修改数组和空间复杂度的要求,可以采用排序数组和哈希表的方法