287_寻找重复数

发表于 分类于 ， 阅读次数： Waline： 本文字数： 1.3k 阅读时长 ≈ 1 分钟

287_寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

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

示例1:

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

输出：2

示例2:

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

输出：3

思路

如果不考虑空间和时间复杂度，可以用哈希表或者排序解决。

我们可以采用142_环形链表II的思路去解决

因为数组num中的数字范围为[1,n],考虑两种情况：

  1. 如果数组中没有重复的数，以数组[1,3,4,2]为例，我们将数组下标n和数nums[n]建立映射关系f(n)
1
2
3
4
o->1
1->3
2->4
3->2

我们从下标0出发，根据f(n)计算出一个值，以这个值为新的下标，以此计算，直到下标越界，这样可以产生一个类似链表一样的序列：

0->1->3->2->4->null

  1. 如果数组中有重复的数，以数组[1,3,4,2,2]为例
1
2
3
4
5
0->1
1->3
2->4
3->2
4->2

0->1->3->2->4->2->4->2...

2->4->2就是一个环

综上：

  1. 数组中有一个重复的数 -> 链表中存在环
  2. 找到数组中的重复数 -> 找到链表的环入口

所以就和前面的环形链表一样，通过快慢指针找到环入口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while(true) {
            slow = nums[slow];
            fast = nums[nums[fast]];

            // 存在环
            if(slow == fast) {
                break;
            }
        }
        int finder = 0;
        // 同时走
        while(slow != finder) {
            finder = nums[finder];
            slow = nums[slow];
        }
        return slow;
    }
};