题目描述

blablabla

样例

blablabla

算法1

(y总方法) $O(n^2)$

时间复杂度

O(n)

参考文献

C++ 代码

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[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
            //i != nums[i] && nums[nums[i]] != nums[i],这一步就是为了调整顺序，可改为上述判断条件
            if(i != nums[i]) return nums[i];
            //i != nums[i] && nums[nums[i]] == nums[i],进行比对，判断是否不同，不同代表包含重复的
        }
        return -1;
    }
};