3. Duplicate number in array

Find duplicate numbers in the array.

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.

Example 1:

Input: [2, 3, 1, 0, 2, 5, 3] Output: 2 or 3Copy the code

Limitations:

2 <= n <= 100000
Copy the code

The answer:

1, use set set

The simplest way to do this is to add each element of the array to a set, and return it if it has a duplicate element

public int findRepeatNumber(int[] nums) { Set<Integer> set = new HashSet<>(); For (int num: nums) {// If (! set.add(num)) return num; } return -1; }Copy the code

2, sort first to find

The second way to do it is to sort first and then look up, and then if there are duplicates, they must be next to each other, and then you compare them, and if there are duplicates, you just return them

Public int findRepeatNumber(int[] nums) {sort(nums); for (int i = 1; i < nums.length; i++) { if (nums[i] == nums[i - 1]) return nums[i]; } return -1; }Copy the code

3. Use temporary arrays

One obvious feature of this problem is that the numbers are between 0 and n-1, so using the above two methods is definitely not the best choice. Temp temp = temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp temp When the value of temp is greater than 1, a duplicate occurs, and we return it

public int findRepeatNumber(int[] nums) {
    int length = nums.length;
    int[] temp = new int[length];
    for (int i = 0; i < length; i++) {
        temp[nums[i]]++;
        if (temp[nums[i]] > 1)
            return nums[i];
    }
    return -1;
}
Copy the code

4. Put it in the specified position

We can not use temporary array, we put the values in the array nums in traverse on the corresponding position, such as an element is 5, we will put him in the nums in [5], each time you put into the check whether the location in the correct values, if already in the correct values, is repeated, we returned directly.

public int findRepeatNumber(int[] nums) { for (int i = 0; i < nums.length; If (I == nums[I]) continue; if (I == nums[I]) continue; If (nums[I] == nums[I]]) {return nums[I]; } int temp = nums[nums[I]]; nums[nums[i]] = nums[i]; nums[i] = temp; // I = 1; // I = 1; // I = 1; } return -1; }Copy the code