题目描述

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

示例 1:

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

示例 2:

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

说明:

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

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

解法1

首先,题目说了不能更改数组、且空间复杂度为O(1),那么我们就不能够使用排序算法。此外,时间复杂度要求小于O(n^2),就不能够使用暴力法(双重循环遍历每个元素)。

题目描述了有n+1个元素,值域为[1, n],这就提示我们:我们可以用数组内容作为数组的索引。例如nums = [1,3,4,2,2]:

索引 0 1 2 3 4
内容 1 3 4 2 2

从索引为0开始,使用数组内容作为索引遍历:
nums[0] = 1
nums[1] = 3
nums[3] = 2
nums[2] = 4
nums[4] = 2
nums[2] = 4
nums[4] = 2
......
可以看出重复序列为[2,4,2,4,...],我们将重复序列绘制成图,如图1所示。
图1 数组内容出现序列

我们再举例nums = [3,1,3,4,2]:

索引 0 1 2 3 4
内容 3 1 3 4 2

从索引为0开始,使用数组内容作为索引遍历:
nums[0] = 3
nums[3] = 4
nums[4] = 2
nums[2] = 3
nums[3] = 4
nums[4] = 2
nums[2] = 3
nums[3] = 4
......
可以看出重复序列为[4,2,3,4,2,3,...]

我们可以看出,如果数组包含重复元素,使用数组内容作为索引会产生重复序列。我们将数组内容按照顺序绘制成图,如图2所示。

图2 数组内容出现序列

对于序列中是否重复的判定,有很多方法可以实现。在这里,我们使用Floyd’s cycle-finding algorithm来实现判圈。该算法很简单,使用快慢指针指向圈的节点,慢指针一次移动一步,快指针一次移动两步,当两个指针相遇时就可以得知存在环路。

如果数组中存在重复元素,那么将遍历序列绘制成图将会形成环路。而进入环路的起点正是数组的重复元素。为了寻找环路的起点,我们将慢指针重新移动到起点,之后,快指针与慢指针每次都只移动一步,当他们再次相遇,就是环路的起点。

下面这张图,给出了该方法能够找到环路起点的证明:

图3 寻找环路起点证明

根据分析,我们能够编写出如下代码。

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0], fast = nums[nums[0]];

        // 快慢指针找到相遇点
        while (nums[slow] != nums[fast]) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        // 将慢指针移动到起点,寻找圈的入口
        slow = 0;
        while (nums[slow] != nums[fast]) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return nums[slow];
    }
}

参考:

  1. https://blog.yxwang.me/2008/09/find-head-in-circular-linked-list/
  2. https://en.wikipedia.org/wiki/Cycle_detection

Leave a Reply

Your email address will not be published. Required fields are marked *