数组中重复的数字（剑指Offer）

题干

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是第一个重复的数字2。没有重复的数字返回-1。

思路

将值为 i 的元素调整到第 i 个位置上进行求解。在调整过程中，如果第 i 位置上已经有一个值为 i 的元素，就可以知道 i 值重复。

代码（java）

import java.util.*;
public class Solution {
    public int duplicate (int[] nums) {
        int n = nums.length;
        if (nums == null || n <= 0)
            return -1;
        //由于题干要求 找出数组中第一个重复的数字，newNums用来保存数组原来的位置
        int[] newNums = Arrays.copyOf(nums, nums.length);
        //set用来存储重复数字的集合
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < n; i++){
            //当下标与值不相等时
            while(nums[i] != i){
                //如果第 i 位置上已经有一个值为 i 的元素, 则 i 值重复，加入set
                if(nums[i] == nums[nums[i]]){
                    set.add(nums[i]);
                    break;
                }
                //交换下标为i与nums[i]的元素
                swap(nums, i, nums[i]);
            }
        }
        //遍历 原数组，第一个出现在 set中的数字就是第一个重复的数字
        for(int i = 0; i < n; i++){
            if(set.contains(newNums[i])){
                return newNums[i];
            }
        }
        //没有重复的数字返回-1
        return -1;
    }
    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}