Find the 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 或 3
Copy the code

Limitations:

2 <= n <= 100000
Copy the code

The number in the range of 0 ~ n-1 is restored to the corresponding position, for example, the number 2 is exchanged to the position with the subscript 2.

If a duplicate is found during the exchange, return directly.

class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0, n = nums.length; i < n; ++i) {
            while(nums[i] ! = i) {if (nums[i] == nums[nums[i]]) returnnums[i]; swap(nums, i, nums[i]); }}return -1;
    }

    private void swap(int[] nums, int i, int j){ int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }}Copy the code