Come to sword finger offer 03. Repeated numbers in the array

Column Preface :

This column is mainly about algorithm training , The goal is simple . But the process needs persistence , It depends on whether we can persist to the end , Become the darker one , Find that feeling .

Find the repeated numbers in the 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 .

Example ：
Example 1：

 Input ：
[2, 3, 1, 0, 2, 5, 3]
 Output ：2  or  3 

Limit ：

2 <= n <= 100000

Problem solving 1：

Sort the array , Look up numbers one by one , If the same, output , The difference moves back at the same time .

class Solution {
    
    public int findRepeatNumber(int[] nums) {
    
        Arrays.sort(nums);
        int low = 0, fast = 1;
        while(fast < nums.length){
    
            if(nums[low] != nums[fast]){
    
                low++;
                fast++;
            }else{
    
                return nums[low];
            }
        }
        return -1;
    }
}

Time O(nlog_n)
Space O(logn)

Problem solving 2：

utilize Hashset To record the numbers in the array , If the number exists in the hash table, output , Otherwise, add the number to Hash In the table .

class Solution {
    
    public int findRepeatNumber(int[] nums) {
    
        Set<Integer> temps = new HashSet<>();
        for(int num:nums){
    
            if(temps.contains(num)){
    
                return num;
            }
            temps.add(num);
        }
        return -1;
    }
}

Time complexity O(N) ： Traversal array use O(N) ,HashSet Add and find elements are O(1).
Spatial complexity O(N) ： HashSet Occupy O(N) The size of the extra space .