Duplicate numbers in array

Title Description : At a length of n Array of nums All the numbers in 0～n-1 Within the scope of . Some numbers in the array are repeated , But I don't know how many numbers are repeated , I don't know how many times each number has been repeated . Please find any duplicate number in the array

Method 1 description of ideas ： The easiest thing to think of is the violent solution , But there is no simpler way ？ We can use map, Add elements from the array to map in , When adding, first judge whether this key value is true , If it is true , Indicates that the element already exists , This element is repeated ; If it's not true , It means that it is the first time to add , Set to true .

Code implementation ：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, bool> map;
        for(int num : nums) {
            if(map[num]) return num;
            map[num] = true;
        }
        return -1;
    }
};

Method 2 ： The time complexity and space complexity of method 1 are O(n), We can try to reduce its spatial complexity

Description of ideas ： At a length of n In the array nums All the numbers in 0~n-1 Within the scope of . Description of this meaning ： The index and value of array elements are one to many . therefore , Make the index of the element correspond to the value one by one . thus , You can map the corresponding value through the index , Play a role equivalent to a dictionary .

Ergodic , First encounter number xx when , Swap it to the index xx It's about ; And when you encounter numbers for the second time xx when , There must be nums[x] = xnums[x]=x , At this point, you can get a set of repeated numbers .

What we need to pay attention to here is only nums[i]==i When i Only then increases progressively , This is to ensure that the processing of some elements will not be missed until the same elements are found .

Code implementation ：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int i = 0;
        while(i < nums.size()) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i])
                return nums[i];
            swap(nums[i],nums[nums[i]]);
        }
        return -1;
    }
};