287.寻找重复数

发表于 | 分类于
字数统计: 565 | 阅读时长 ≈ 2

一、题目描述

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

示例 1:

1
2
输入: [1,3,4,2,2]
输出: 2

示例 2:

1
2
输入: [3,1,3,4,2]
输出: 3

说明：

  1. 不能更改原数组（假设数组是只读的）。
  2. 只能使用额外的 O(1) 的空间。
  3. 时间复杂度小于 O(n2) 。
  4. 数组中只有一个重复的数字，但它可能不止重复出现一次。

二、题解

1.算法描述

  • 快指针&慢指针

2.个人分析

  • 将此题抽象成环型链表问题（见141题、142题）

    那么如何在数组中模拟快慢指针呢？

    看了题解：

    1
    2
    fast = nums[nums[fast]];
    slow = nums[slow];
    1
    2
    3
    4
    slow = 0;fast = 0;
    nums[] = [3,1,3,4,2]
    nums[slow] = [3,4,2,3]
    nums[nums[fast]] = [4,3,2,4]

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int findDuplicate(int *nums, int numsSize)
{
    int slow = 0, fast = 0;
    while (true) //一定有相同元素，所以死循环
    {
        fast = nums[nums[fast]]; //快指针
        slow = nums[slow];       //慢指针
        if (slow == fast)        //快慢指针相遇，开始寻找成环入口，即为重复的数
        {
            fast = 0;
            /*寻找环的入口
                nums[slow] == nums[fast]时，快慢指针指向的元素相等，即为所求元素
                快慢指针指向的元素不等时，则继续寻找*/
            while (nums[slow] != nums[fast])
            {
                fast = nums[fast];
                slow = nums[slow];
            }
            return nums[slow];
        }
    }
}

三、PS

这是一道中等难度的题目，我还不是很理解。完全参考了作者SEU.FidGet的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findDuplicate(int[] nums) {
        /**
        快慢指针思想, fast 和 slow 是指针, nums[slow] 表示取指针对应的元素
        注意 nums 数组中的数字都是在 1 到 n 之间的(在数组中进行游走不会越界),
        因为有重复数字的出现, 所以这个游走必然是成环的, 环的入口就是重复的元素, 
        即按照寻找链表环入口的思路来做
        **/
        int fast = 0, slow = 0;
        while(true) {
            fast = nums[nums[fast]];
            slow = nums[slow];
            if(slow == fast) {
                fast = 0;
                while(nums[slow] != nums[fast]) {
                    fast = nums[fast];
                    slow = nums[slow];
                }
                return nums[slow];
            }
        }
    }
}