Duplicate numbers in the array of sword finger offer 03

《 The finger of the sword offer 03》 Repeated numbers in an array

【leetcode link 】

Repeated numbers in an array

【 subject 】

Find the repeated numbers in the array .

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 .

Example 1：

Input ：

[2, 3, 1, 0, 2, 5, 3]

Output ：

2 or 3

【 Ideas 】

Review the topic carefully and know ,nums All the numbers in the are in 0~n-1 in , So every number in the array will have a subscript equal to its value corresponding to it , As shown in the figure below ：

Therefore, we can judge whether the elements are repeated by matching the corresponding elements with the following table in turn and judging whether the subscript element values corresponding to the current element and the current element values are the same .

The specific steps are as follows ：

What we should pay attention to here is , When we exchange elements , You also need to check whether the current element matches the current subscript , Because this exchange operation can only ensure that the elements exchanged in the past correspond to their subscripts , There is no guarantee that the exchanged elements correspond to the subscripts here . Only the front element corresponds to the subscript , It is possible to find duplicate elements later .

Last , If the repeated elements are not found after traversing the array, it means that there are no repeated elements .

【 Code implementation 】

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

【 Time complexity & Spatial complexity 】

For time complexity , Although one in the code for Loop a while loop , however while The number of cycles is constant , So the time complexity is O(N)

In terms of time complexity , Although one in the code for Loop a while loop , however while The number of cycles is constant , So the time complexity is O(N)

Because we don't use extra space in the code , So the complexity of space is O(1).