class Solution {
    public int duplicateInArray(int[] nums) {

        int n = nums.length;
        //把nums[i]放到数组下标为i上
        //每次交换都会确定一个数放在了正确的i上
        //保证i != nums[i] && nums[nums[i]] != nums[i]
        //当不可交换的时候 ， 如果nums[nums[i]] == nums[i]说明有重复的出现了
        for(int i = 0 ; i < n ; i++) if(nums[i] < 0 || nums[i] > n - 1) return -1;

        for(int i = 0 ; i < n ; i++){
            while(i != nums[i] && nums[nums[i]] != nums[i]){
               // swap(nums[nums[i]] , nums[i]);
               int temp = nums[nums[i]];
               nums[nums[i]] = nums[i];
               nums[i] = temp;
            } 
            if(i != nums[i] && nums[nums[i]] == nums[i]) return nums[i];
        }
        return -1;
    }

    // public static void swap(int i , int j ){
    //     int temp = i;
    //     i = j;
    //     j = temp;
    // }
}