1. Title Description

All numbers in an array of length N, nums, are in the range 0 to n-1. Some numbers in the array are repeated, but we don’t know how many are repeated, or how many times each number is repeated. 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 a duplicate of the numbers 2 or 3. If there are no duplicate numbers, return -1;

2. How to solve the problem

1, sorting,

Just sort the input array, scan the sorted array from beginning to end, and use quicksort to sort an array of length N takes O(nlogn) time and space complexity O(1).

2, hash table

Algorithm that

In Java, you can use a HashSet to store elements directly, storing all elements in the set one at a time, and returning false when the set already exists, in which case the element is a duplicate element.

Code implementation

public int findRepeatNumber(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    int len = nums.length;
    for(int i = 0; i<len; i++){if(! set.add(nums[i])){returnnums[i]; }}return -1;
}
Copy the code

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: O(n)

3, in situ replacement

Algorithm that

The number ranges from 0 to n-1. If there are no duplicate numbers in the array, the number I will appear at the subscript I when the array is sorted. Remember the number of position I as m. If I and M are not equal, judge whether NUMs [m] and M are equal. If they are equal, find the first repeated number; if they are not equal, switch m and NUMs [m] and continue scanning from the position of I.

Algorithm process

  1. Scan the array from beginning to end, and when you find a number with subscript I, first compare whether that number (denoted by m) is equal to I.
  2. If so, the next number is scanned;
  3. If not, compare it with the MTH number;
    • If it is equal to the MTH digit, the first repeated digit is found (both the subscript I and m positions occur);
    • If it’s not equal to the MTH digit, you swap the i-th digit with the MTH digit, and you put m in its place.
  4. Repeat the comparison and swap process until we find the first repeated number. Otherwise -1 is returned.

Code implementation

public int findRepeatNumber(int[] nums) {
    int i = 0;
    int len = nums.length;
    int temp;
    while(i<len){
        if(nums[i]! =i){if(nums[i] == nums[nums[i]]){
                return nums[i];
            }
            temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }else{
            i+=1; }}return -1;
}
Copy the code

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: O(1)