数组中重复的数字

1628439994(1).png

分析：（萝卜去找坑，而不是坑找萝卜）
一共n个数，都在0-n-1范围， 如果没有重复，按道理就是每个下标一一对应一个数。也就是一个萝卜一个坑的思想，我们就假设这样，重头遍历，给每一个萝卜归位，归位的方式为：
比如当前遍历到0号坑，上面是3号萝卜，那就把0号和3号坑的萝卜交换下，此时，3号坑的萝卜对劲了，但是3号坑的萝卜不知道是多少，可能0号萝卜，也可能是其他的，前者那就直接完成任务，后者就要继续重复这个操作，知道有一次，发现交换的坑位上的萝卜已经是对劲的了，说明当前的萝卜多余了。

代码：

class Solution {
    public int findRepeatNumber(int[] nums) {
        //逐个给每个萝卜找自己的坑位，同时也给在坑位上的其他萝卜归位
        for(int i=0;i<nums.length;i++){
            while(nums[i]!=i){
                if(nums[i]==nums[nums[i]]){
                    //比如i=0，nums[i]=2,然后nums[2]也已经有2了，有两个同样的萝卜
                    return nums[i];
                }
                else{
                    swap(nums,i,nums[i]);
                }
            }
        }
        return -1;
    }

    public void swap(int[] nums, int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}