剑指 Offer——面试题 3-1

题目

找出数组中的重复数字

在一个长度为n的数组里的所有数字都在0 ~ n - 1的范围内，数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次，请找出数组中任意一个重复的数字

输入样例

1	[2, 3, 1, 0, 2, 5, 3]

输出样例

2 或 3

思路

这道题是一个很常见的数组问题，解法也有很多种，

首先想到的我们可以通过暴力方法（手动狗头），我们排序这个数组，然后遍历一遍数组看看有没有连续的两个相同的数字；另外，我们可以通过哈希表的特性，在遍历数组的过程中，每次检测哈希表中是否存在这个数字，不存在就放入哈希表中，存在就直接返回这个重复元素

那有没有什么比较巧妙的方法呢嘿嘿

这里提供一种方法，首先，如果这个数组没有重复元素，那么它一定会包含0 ~ n - 1中的所有数字，那么我们从头开始遍历这个数组，每遇到一个数，就检测它是不是在自己的位置上，即数组为nums，循环变量是i，当我们遍历到nums[i]时，我们检测nums[i] == i，如果不相等，我们就把nums[i]放到nums[i]的位置上，这样，在继续遍历的过程中，如果第二次遇到一个相同的数字，就会出现nums[i] == nums[nums[i]]这种情况，此时就是重复的数字了！代码如下：

代码

#include <iostream>

using namespace std;

bool dublicate(int numbers[], int length) {
	if (numbers == nullptr || length <= 0)
		return false;
	for (int i = 0; i < length; ++i) {
		while (numbers[i] != i) {
			if (numbers[i] == numbers[numbers[i]])
				return true;
			int item = numbers[numbers[i]];
			numbers[numbers[i]] = numbers[i];
			numbers[i] = item;
		}
	}
	return false;
}

int main() {
	int a[5] = { 1, 2, 3, 3, 4 };
	if (dublicate(a, 5))
		cout << "yes" << endl;
	else
		cout << "no" << endl;
}