13. 找出数组中重复的数字
https://www.acwing.com/problem/content/14/
思路:
由于数据范围在0-n-1,如果出现的数字都只有一次 我们可以构造出0,1,2,,,n-1的数组
所以我们每次循环吧数字交换到对应值的下标 操作完毕后查看是否满足nums[i]=i
如果不行说明是重复数字
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int n=nums.size();
for(auto x:nums){
if(x<0 || x>=n) return -1;
}
for(int i=0;i<n;i++){
while(nums[i]!=nums[nums[i]]){
swap(nums[i], nums[nums[i]]);
}
if(nums[i]!=i) return nums[i];
}
return -1;
}
};