题目:
在一个长度为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>