算法1

(遍历) $O(n^2)$

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size() ;
        for(auto x : nums)
        if(x < 0 ||x > n-1) 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 && nums[i] == nums[nums[i]])
          return nums[i];
        }
        return -1;
    }
};