03 数组中重复的数字

Lin2J
2021-07-19 / 0 评论 / 95 阅读
温馨提示:
本文最后更新于2021-07-19,若内容或图片失效,请留言反馈。

剑指 Offer 03. 数组中重复的数字

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

方法一:使用集合

遍历数组,对于每个数字,先判断集合中是否有该数字,如果没有则存入集合中,如果已经存在了,那么该数字就为重复的数字。

代码:

public int findRepeatNumber(int[] nums) {
    if (nums == null || nums.length == 1) {
        return -1;
    }
    Set<Integer> set = new HashSet<>();
    for (Integer n : nums) {
        if (set.contains(n)) {
            return n;
        } else {
            set.add(n);
        }
    }
    return -1;
}

复杂度分析

  • 时间复杂度$O(N)$:最坏的情况下,需要进行 $N$ 次循环,HashSet 的添加和查找都是 $O(1)$ 的。

  • -空间复杂度$O(N)$:HashSet 占用 $O(N)$ 大小的空间。

方法二:原地交换

题目中说明了这个长度为 $N$ 的数组中的数字的范围在 $[0, N-1$ 中,因此假如每个数字都是唯一的,那么必定会有 $nums[i] = i$ 。

现在题目中说明了有数字重复了,那么我们在遍历数组的时候,遍历到数字 $a$ 时,将 $a$ 交换到索引 $a$ 处,此时有 $nums[a] = a$ ​。那么第二次遇到数字 $a$ 时,一定有 $nums[a] = a$ 了,所以 $a$ 一定是重复的数字。

算法流程:

  1. 遍历数组 $nums$,初始索引位置 $i = 0$。
    1. 若 $nums[i] = i$ :说明 $nums[i]$ 已经在对应索引位置上了,无需交换。
    2. 若 $nums[nums[i]] = nums[i]$ :说明 $nums[i]$​ 处和索引 $i$ 处的元素值都为 $nums[i]$ ,那么 $nums[i]$ 就是一个重复的数字,返回值 $nums[i]$ 。
    3. 否则,交换索引 $i$ 和 $nums[i]$ 的元素值,将此数字交换至对应索引位置。
  2. 若遍历完尚未返回,则返回 $-1$。

代码:

public int findRepeatNumber(int[] nums) {
    if (nums == null || nums.length == 1) {
        return -1;
    }
    for(int i = 0; i < nums.length;) {
        if(nums[i] == i) {
            i++;
            continue;
        }
        if(nums[nums[i]] == nums[i]) {
            return nums[i];
        }
        int tmp = nums[nums[i]];
        nums[nums[i]] = nums[i];
        nums[i] = tmp;
    }
    return -1;
}

复杂度分析

  • 时间复杂度 $O(N)$: 需要循环 $N$ 遍,每轮的判断和交换操作是 $O(1)$。

  • 空间复杂度 $O(1)$: 使用常数级的空间。