题目描述：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1
数据范围：0≤n≤10000
进阶：时间复杂度O(n) ，空间复杂度O(n)
示例：
输入：
[2,3,1,0,2,5,3]
返回值：
2
说明：
2或3都是对的
解题思路：
本题是排序类题目，四种解题思路：
1）暴力法
双循环遍历，找到重复数字返回。时间复杂度O(n^2)，空间复杂度O(1)。
2）排序遍历法
用快速排序将数组排序，再遍历搜索。时间复杂度O(nlogn)，空间复杂度O(1)。
3）哈希表
用哈希表判断数字是否重复，可以用哈希set或者哈希map。哈希表查询O(1)，所以只需遍历一轮即可完成。时间复杂度O(n)，空间复杂度O(n)。
4）下标哈希法
将数组下标作为哈希键，比如数字2就把它放在数组下标2的位置，原先下标2位置的数字移动到数字2本来的位置，完成交换；依次类推，直到某次交换发现数字x和下标x的数字冲突了，说明找到重复值了；最坏的情况就是没有重复数字，把所有下标都遍历交换过一轮。时间复杂度O(n)，空间复杂度O(1)。
注意：应用该方法的前提是如题目给定的条件那般，数字大小范围在0到n-1之间，不然就越界了。
测试代码：
1）暴力法
class Solution { public: // 寻找重复数据 int duplicate(vector<int>& numbers) { int size= int(numbers.size()); for (int i = 0; i < size; ++i){ for (int j = i + 1; j < size; ++j){ if (numbers[i] == numbers[j]) return numbers[i]; } } return -1; } };
2）排序遍历法
class Solution { public: // 寻找重复数据 int duplicate(vector<int>& numbers) { // 快排 sort(numbers.begin(),numbers.end()); int size = int(numbers.size()); // 寻找重复值 for(int i = 1; i <size; ++i){ if(numbers[i] == numbers[i - 1]) return numbers[i]; } return -1; } };
3）哈希表
class Solution { public: // 寻找重复数据 int duplicate(vector<int>& numbers) { // 哈希set unordered_set<int> us; int size = int(numbers.size()); for(int i = 0; i < size; ++i){ if(us.count(numbers[i])) return numbers[i]; else us.insert(numbers[i]); } return -1; } };
4）下标哈希法
class Solution { public: // 寻找重复数据 int duplicate(vector<int>& numbers) { // 下标哈希法 int size = int(numbers.size()); for(int i = 0; i < size;){ if(numbers[i]==i) i++; else{ if(numbers[numbers[i]] == numbers[i]) return numbers[i]; else{ swap(numbers[numbers[i]], numbers[i]); } } } return -1; } };
