寻找重复数

力扣 287. 寻找重复数

题目说明

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

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

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

提示：

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

示例

示例 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

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现题目要求的是至少出现一个，所以就不能使用位运算了，这里可以将这个数组看成循环数组，然后使用快慢指针求解，让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * 双指针
     */
    public int findDuplicate(int[] nums) {
        // 将出现重复元素的数组看成环，用快慢指针来查找重复出现的那个节点
        int slow = 0;
        int fast = 0;

        while (slow != fast || fast == 0) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        slow = 0;
        while (nums[slow] != nums[fast]) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return nums[slow];
    }
}