题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

样例

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

算法1

(按索引枚举) $O(n)$

题目中说到:nums 数组中的所有数字都在0 ~ n-1 范围内.
数组的长度也只有n,对应索引范围在0 ~ n-1 范围内。所以我们可以利用一个nums[i] 放入到索引i 中,当下一次又有一个数要放入到i 索引的时候，说明这个数就是重复的数。

算法流程：
1.当前索引i == nums[i],那么就说明此时的nums[i] 已经在对应的索引上了，不需要动它。
2.当索引i != nums[i],那么我们就要以nums[i] 作为索引，找到nums[nums[i]] = nums[i] 的位置了，注意：如果此时nums[nums[i]] 位置上不等于nums[i],说明nums[nums[i]]
位置要没被动过，也证明此时nums[i] 可以移动到nums[nums[i]] 位置。
如果nums[nums[i]] == nums[i],那么这个nums[i] 就是我们要找的重复数字。

时间复杂度

O(n)

参考文献

Java 代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++){
            if(i != nums[i] && 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;
    }
}