题解 | #数组中重复的数字#

题目：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1。

1.排序法 （允许改变数组）
先进行排序，再相邻元素进行等值判断。
时间复杂度：O(nlogn)
空间复杂度：O(1)

2.hash方法（没有改变数组）
解题思路：
(1) 声明hash表
(2) 使用数组构造哈希表
(3)对哈希表的value进行判断，若大于1，即表明数字重复出现
int duplicate(vector<int>& numbers)
{
if(numbers.size() == 0) return -1;
unordered_map<int, int> map;
for(int i =0; i < numbers.size(); i++)
{
map[numbers[i]]++;
if(map[numbers[i]]> 1) return numbers[i];
}
return -1;
}
时间复杂度：O(n),一层循环
空间复杂度：O(n)，最坏情况，没有元素重复，hash表需要存所有的值，即需要O(n)空间存储所有元素</int>

3.替换法
关键是:数组长度为n，且所有数字范围在0~n-1之间。因此如果数字没有重复，那numbers[i] = i;
思路是：如果进行了正常的排序，那么i与对应的数字是相同的，本题的巧妙在于swap(numbers[i], numbers[numbers[i]])实现了前面所说的对应关系。
int duplicate(vector<int>& numbers)
{
if(numbers.empty()) return -1;
for(int i = 0; i < numbers.size(); i++)
{
while(numbers[i] != i)
{
if(numbers[i] == numbers[numbers[i]])
{
return numbers[i];
}
else{
swap(numbers[i], numbers[numbers[i]]);
}
}
}
return -1;
}
时间复杂度：O(n)
空间复杂度：O(1)</int>