题目描述

n个数字组成的数组，数组大小在 在 0～n-1的范围内

样例

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        for(auto a : nums)
            if(a < 0 || a >=n ) return -1;

        for(int i = 0; i < n; i++)
        {
            // 我不在我应该在的位置  而且我应该在的位置上的值不是我 那
            while(nums[i] != i && 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;
    }
};
// 原地交换  
// O(2n) + O(1)

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        vector<int> hash(n);

        for(auto a : nums)
        {
            if(a < 0 || a >=n ) return -1;
            hash[a]++;
            if( hash[a] > 1 ) return a;          
        }

        return -1;
    }
};
// 哈希
// O(n) + O(n)

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());

        for(int i = 0; i < n; i++)
        {
            if(nums[i] < 0 || nums[i] >=n ) 
                return -1;
            if( i + 1 < n && nums[i] == nums[i+1]) 
                return nums[i];          
        }
        return -1;
    }
};
// 排序后遍历
// O(nlogn + n) + O(1)