题解 | #数组中重复的数字#
数组中重复的数字
https://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524
描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。
数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1
数据范围：0≤n≤10000 0\le n \le 10000 \0≤n≤10000
进阶：时间复杂度O(n) O(n)\O(n) ，空间复杂度O(n) O(n)\O(n)
输入：
[2,3,1,0,2,5,3]返回值：
2
说明：
思路：1 从头到尾对元素进行便利，将i处的值与 i值的索引处的number比较，相等则return该值，否则交换两者的位置
2或3都是对的
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型vector
* @return int整型
*/
int duplicate(vector<int>& numbers) {
int size = numbers.size();
int i =0;
while(i<size){
if(numbers[i]==i){
i++;
}
else{
if(numbers[i]== numbers[numbers[i]]){
return numbers[i];
}
else{
swap(numbers[i], numbers[numbers[i]]);
i++;
}
}
}
return -1;
}
};
