剑指offer03-1（重复数字）

发表于 | 分类于 ，

题目：

　　在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。
也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么
对应的输出是第一个重复的数字2。

思路：

　　对于重复数字问题常规解法有先排序后比较相邻数字，或者利用哈希表，但这两种解法前者需要O(nlogn)的时间复杂度，
后者需要O(n)的空间复杂度，时空复杂度没有达到最佳。但此题给出了特殊的条件：所有数字都在0到n-1的范围内。利用
此条件可以优化时间复杂度。具体实现见代码。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean duplicate1(int numbers[],int length,int [] duplication) {
	for(int i = 0;i < length;i++) {
		if (numbers[i] != i) {
			if (numbers[numbers[i]] == numbers[i]) {
				duplication[0] = numbers[i];
				return true;
			}
			int temp = numbers[i];
			numbers[i] = numbers[temp];
			numbers[temp] = temp;
		}
	}
	return false;
}

复杂度分析及总结：

循环：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。