剑指offer03-2（重复数字）

发表于 | 分类于 ，

题目：

　　在一个长度为n+1的数组里的所有数字都在1~n的范围内，找出数组中的任意一个重复数字，但不能修改原数组。

思路：

　　由于题目要求不可以修改原数组，故不可用先排序再找重复数字的思路，也不可用Offer03-1中的思路。因此可以考虑使用特殊的哈希表，
即同样大小的数组，将原数组的数字放在对应的索引处，但需要O(n)的空间。利用此题的特殊条件：所有数字都在1n的范围内，可以想到利用二分法
寻找。n+1个数字在1n的范围内，所有1n中必定有重复数字，取1n的中间值mid，若1mid的数量大于mid，则重复数字必定在1mid中，这便是二分法
的典型思路。

代码：

二分法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int getDuplication(int[] nums,int length) {
	int start = 1;
	int end = length - 1;
	while(start <= end) {
		int mid = (start + end) >> 1;
		int count = countRange(nums, start, mid);
		if (start == end) {
			if (count > 1) {
				return start;
			}else {
				break;
			}
		}
		if (count > mid - start + 1) {
			end = mid;
		}else {
			start = mid + 1;
		}
	}
	return -1;
}
public static int countRange(int[] nums,int start,int end) {
	int count = 0;
	for(int i = 0;i < nums.length;i++) {
		if (nums[i] >= start && nums[i] <= end) {
			count++;
		}
	}
	return count;
}

复杂度分析及总结：

循环：

　　时间复杂度：
　　　　O(nlogn)。
　　空间复杂度：
　　　　O(1)。
　　与利用哈希表相比，此方法用时间换取了空间。