3. 数组中重复的数字

题目要求：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
数组中某些数字是重复的，请找出数组中任意一个重复的数字。

解题思路：
置换法。题目中说明nums值在[0, n-1]之内，我们能充分利用这个条件：将元素置换到对应索引的位置上（即array[i] = i）
若在从左往右遍历过程中，发现当前元素（值为i）即将要被置换的位置上（array[i]），已经满足了array[i] = i，说明重复。

特别注意：
1、置换完成后，指针需要重新回退一格，使得下次遍历重新检查置换后的元素。
2、在进行array[i]和array[array[i]]置换时（利用中间变量temp），不能先将array[i]赋值。这会改变array[array[i]]想要表达的位置。

C++

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int len = nums.size();
        int i = 0;
        for(;i < len;i++){
            if(nums[i] != i){
                if(nums[nums[i]] == nums[i]) break;
                else{
                    int temp = nums[nums[i]];
                    nums[nums[i]] = nums[i];
                    nums[i] = temp;
                }
                i--;
            }else continue;
        }
        return nums[i];
    }
};

Java

class Solution {
    public int findRepeatNumber(int[] nums) {
        int len = nums.length;
        System.out.print(len);
        int i = 0;
        for(;i < len;i++){
            if(nums[i] != i){
                if(nums[nums[i]] == nums[i]) break;
                else{
                    // 不能先赋值给nums[i]，否则nums[nums[i]]无法得到正确值
                    int temp = nums[nums[i]];
                    nums[nums[i]] = nums[i];
                    nums[i] = temp;
                }
                i--;
            }else continue;
        }
        return nums[i];
    }
}