All the numbers in an array of length N are in the range 0 to n minus 1. Some numbers in the array are duplicated, but it is not known how many are duplicated. I don’t know how many times I repeat each number. Please find any duplicate number in the array. For example, if you input an array of length 7 {2,3,1,0,2,5,3}, the corresponding output is the first repeated number 2.

A hashmap method

We can use a HashMap to store the values of the array and the number of occurrences, which is repeated when the number of occurrences is greater than 1. This is easy.

Java’s Set method

We can use the set’s own capabilities for reprocessing. If you cannot add an element to a set, it is repeated.

public int findRepeatNumberV2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if(! set.add(num)) {returnnum; }}return -1;
    }
Copy the code

New Array method

If we look at the problem carefully, we’ll notice that the condition that all the numbers are in the range of 0 to n minus 1, which is the condition that usually happens, we’ll think about using an array, because this condition limits the range of numbers, and you can match the index of the array to the number.

We can initialize an array data[n], and scan the input number to determine whether data[number] is 0. If the value is 0, increment the data[number] by 1 to indicate that the number already exists.

 public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || numbers.length <= 1) {return false;
        }
        int[] value = new int[length];
        for (int i = 0; i < length; i++) {
            int number = numbers[i];
            if (value[number] == 1) {
                duplication[0] = number;
                return true;
            }else{ value[number]++; }}return false;
        
    }
Copy the code

Array in place swap comparison method

This range is the same as the index range of the array. If there are no duplicate numbers, then the two ranges should be one-to-one, but because there are duplicate numbers, then there is a many-to-one relationship.

public int findRepeatNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        for (int i = 0; i < nums.length;) {
            int value = nums[i];
            if(value ! = i && nums[value] == value){// If nums[value] is not equal to index I, and nums[value] is the same value, it is repeated.
                return value;
            } else if(value ! = i) {// Otherwise, nums[value] and nums[I] are exchanged
                Utils.swap(nums,value,i);
            }else{ i++; }}return -1;
    }
Copy the code

So how does this code work

The initial array is {2,3,1,0,2,5,3}

  1. Nums [2] = {1,3,2,0,2,5,3}; nums[0] = {1,3,2,0,2,5,3}

  2. Nums [0] = {3,1,2,0,2,5,3}

  3. Repeat the comparison, this swap is {0,1,2,3,2,5,3}

  4. Nums [2] = nums[2]; nums[2] = nums[4]; nums[2] = nums[4]; nums[2] = nums[2]; Return.

Analysis of four methods

The first three methods are similar in that they use extra space.

The fourth method operates directly on the original array without using extra space.