Leetcode 287.寻找重复数

题目描述：

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

进阶：

• 如何证明 nums 中至少存在一个重复的数字?
• 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

示例 1：

1
2

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

1
2

输入：nums = [3,1,3,4,2]
输出：3

示例 3：

1
2

输入：nums = [1,1]
输出：1

示例 4：

1
2

输入：nums = [1,1,2]
输出：1

提示：

• $1 <= n <= 10^5$
• $nums.length == n + 1$
• $1 <= nums[i] <= n$
• nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

链接：

https://leetcode-cn.com/problems/find-the-duplicate-number

题目分析

  使用抽屉原理就可以证明进阶要求的第一问，不再赘述。
  题目要求不能修改原数组，且只能用常量级的空间，那么排序做法、哈希做法都是不能用的。由于没有仔细看提示（只研究了一下 1 到 n 的和会不会超过 int 上限），并且给出的示例也不够好，以为重复的那个数出现了两次，那么其他数就刚好都出现一次，直接使用数组总和减去 1 到 n 的和，打码测试示例提交一气呵成，以为秒杀却非常悲惨地收到一个 WA。
  这下明白了，重复的数字是可以出现多次的，也即是说，其他数字也可以不出现，这下就比较难用到 1 到 n 的一些性质了。我们通过一个萝卜一个坑的原理思考一下可行性，如果使用 nums[i] 与 i 之间的映射会出现什么情况呢？我们把它们的这种联系视为链表，则重复的那个数字下标，会出现多个指针指向它的情况。我们从下标 0 出发，则如果数字不重复，通过这个映射，我们会得到一条链，而直到重复数字出现，重新指向了之前指向的下标，也就是形成了环。
  注意这里有个很重要的一点，不重复的数字之间通过映射也是可能形成一个首尾相连的环的，但是这些数字不含 0，因此从下标 0 出发一定不会得到首尾相连的环，那么成环的那个就一定是重复的数字了。而且这样的映射数组里的数字不会超过 n，这说明肯定不会形成一条链，那么我们从 0 出发肯定能找到答案。答案就是从 0 出发的链表中环的入口，这样这道题已经转化成了我们做过的一道题 Leetcode 142.环形链表 II。这道题的最佳算法是使用快慢指针，时间复杂度就是 $O(n)$，符合进阶要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int fast = 0, slow = 0;
        do{
            fast = nums[nums[fast]];
            slow = nums[slow];
        }while(fast != slow);
        fast = 0;
        while(fast != slow){
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组的大小。形成的链表大小不会超过 $n$，而找到一条长度为 $n$ 的链表的环入口时间复杂度是 $O(n)$。
  空间复杂度：$O(1)$。我们只是通过映射把原数组视为链表，实际上只需要通过两个变量充当指针的角色在数组中迭代，并没有真正建立链表，需要的空间是常数级的。

  PS：官方题解中还有两种 $O(n\log n)$ 的做法，都是通过 1 到 n 的性质寻找的，分别是记录小于等于 i 的数字个数和使用二进制求出重复数的每一位。成功解决了重复数为多个时带来的影响，还是有借鉴意义的。