题目描述

给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；

样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

方法一直接sort一遍，提前将不在0~n-1的return -1,然后找有没有重复的,时间复杂度O(nlogn)

时间复杂度O(n)的做法，我们首先扫描数组将不符合要求的数组元素删去，然后如果这个点的位置不是它正确的位置，那么我们就判断它正确的位置上的数是否正确，如果不正确，交换，如果正确那么这个数字就是多余的return就好，由于每个数有且只有一次判断是否在正确位置，所以最多执行n次,时间复杂度O(n)

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {

       sort(nums.begin(),nums.end());
       int n=nums.size();
       for(int i=0;i<nums.size();i++)
       {
           if(nums[i]<0||nums[i]>=n)return -1;
           else 
           {
               if(nums[i]==nums[i+1])return nums[i];
           }
       }
        return -1;
    }
};

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {

      int n=nums.size();
      for(auto s:nums)if(s>=n||s<0)return -1;


     for(int i=0;i<n;i++)
     {
         while(i!=nums[i]&&nums[nums[i]]!=nums[i])swap(nums[i],nums[nums[i]]);
         if(i!=nums[i]&&nums[nums[i]]==nums[nums[i]])return nums[i];
     }
     return -1;
    }
};