思路
每一次把num[i]这个位置的数据替换为i
替换方法:把现有的num[i]这个数据放到正确的位置去
如果替换的时候 那个位置的数和这个位置的数是一样的,然后这个位置的数还不是i,就证明这个数是重复的。
时间复杂度
O(n)
C++ 代码
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int a = -1;
for(int i=0;i<nums.size();i++){
int x = nums[i];
if(x<0||x>nums.size()-1)
return -1;
}
for(int i=0;i<nums.size();i++){
while(nums[i] != nums[nums[i]]) swap(nums[i],nums[nums[i]]);
if(nums[i] != i) return nums[i];
}
return -1;
}
};