LeetCode 剑指 Offer 03. 数组中重复的数字 原地部分有序化题解，理解、内化巧妙思路。

题目

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

https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

找出数组中重复的数字。

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

Set集合解

Set（基于Map）非常适合用来数据查重、判断是否存在O(1)，相比使用List结构判断contains复杂度最优。

复杂度分析

时间

遍历一次给定数组，时间复杂度O(n)。

空间

使用了额外的Set集合，空间复杂度O(n)。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public int findRepeatNumberWithSet(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (set.contains(num)) {
            return num;
        }
        set.add(num);
    }
    return -1;
}

原地部分有序化题解

上述使用Set求解，我们未充分利用题干已知条件：

长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内

思路

  • 取值0～n-1的数据，并且数组长度为n，并且其中存在重复元素
  • 已知数组给定是无序的，那么我们尝试有序化，同时，将元素值、元素下标一一对应上
  • 基于上述操作，重复元素在有序化时，第二次一定会产生下标冲突！
  • 有序化具体操作：
    • 我们以i表示数组遍历下标，尝试将当前nums[i]下标有序化；
    • i==nums[i]时，说明当前元素值与下标本身就是匹配的，我们挪动i；
    • i!=nums[i]时：
      • 将下标为nums[i]的元素值替换为i，同时将原下标nums[i]元素值交换到i位置；
      • 如果上述替换操作时发现，nums[i]下标位置的元素值已经是i了，说明是原先已经有一个i值（也可能是刚刚交换过去的），此时即求得重复元素；

这个思路下，一是利用了题干的已知条件，二，实现中未利用多余的集合空间，交换操作也只有O(1)复杂度。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int findRepeatNumber(int[] nums) {
    int n = nums.length;
    // 将nums数据有序化，对齐 i下标与iVal
    int i = 0;
    // 每次将 nums[i]下标的数据归位
    while (i < n) {
        if (nums[i] == i) {
            // 当前i位置值已经有序化
            ++i;
            continue;
        }
        // nums[i]下标的数据归位
        int tmp = nums[nums[i]];
        if (tmp == nums[i]) {
            // 当前nums[i]位置的值已经等于了i位置的值，说明是之前替换或者本来就有序就位的，为所求重复项
            return nums[i];
        }

        nums[nums[i]] = nums[i];
        nums[i] = tmp;
    }
    return -1;
}

复杂度分析

时间

最差也仅需遍历完数组，时间复杂度为O(n)。

空间

本算法操作为原地操作，空间复杂度O(1)。