Sword finger offer03 Repeated numbers in the array [simple]

The finger of the sword Offer 03. Repeated numbers in an array

Title Description ：

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

Limit ：

2 <= n <= 100000

JAVA Code

Common method

Two levels of traversal search for the first repeated number one by one .

class Solution {
    
    public int findRepeatNumber(int[] nums) {
    
        for(int i = 0;i<nums.length-1;i++){
    
            for(int j = i+1;j<nums.length;j++){
    
                if(nums[i]==nums[j]){
    
                    return nums[i];
                }
            }
        }
        return -1;
    }
}

Map Method

Use map Storage nums data , With nums The value of map Of key, When encountering the same key Value returns the value .

class Solution {
    
    public int findRepeatNumber(int[] nums) {
    
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0;i<nums.length;i++){
    
            if(map.containsKey(nums[i])){
    
                return nums[i];
            }
            map.put(nums[i],i);
        }
        return -1;
    }
}

Official methods

Use Set, Store only one value , Than Map Method is simpler to store two values
expand ：Set Disordered and unrepeatable .add() Method returns false, It indicates that there are duplicate values .

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

“ There are no other complicated operations about location , So just storing values is enough .”