数组 - LeetCode 03.数组中重复的数字

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

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

这道题在原书上绝对不是简单级别啊！它考察的是程序员的沟通能力，先问面试官要时间/空间需求！！！

在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。 此说明含义：数组元素的 索引 和 值是 一对多 的关系。

因此，可遍历数组并通过交换操作，使元素的索引与值一一对应（即 nums[i] = i ，索引为i的位置，值是i ）。因而，就能通过索引映射对应的值，起到与字典等价的作用。

image.png

算法流程：

1、遍历数组 nums，设索引初始值为 i = 0:

• 若 nums[i] = i： 说明此数字已在对应索引位置，无需交换，因此跳过；
• 若 nums[nums[i]] = nums[i]： 代表索引 nums[i]处和索引 i 处的元素值都为 nums[i]，即找到一组重复值，返回此值 nums[i]；
• 否则：交换索引为i和 nums[i]的元素值，将此数字交换至对应索引位置

2、若遍历完毕尚未返回，则返回 -1

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]){
                // 已找到重复数字
                return nums[i];
            } 
            // 把num[i]的值换到它该有的位置，比如num[i]的值是2, 就把num[i]的值放到下标为2的位置
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }
}

IMG_0002.jpeg

复杂度分析：

• 时间复杂度 O(N)： 遍历数组使用O(N) ，每轮遍历的判断和交换操作使用 O(1)。
• 空间复杂度 O(1)： 使用常数复杂度的额外空间。