力扣最热一百题——寻找重复数（中等）

题目链接：287. 寻找重复数 - 力扣（LeetCode）

题目描述

示例

提示：

解法一：暴力搜寻

Java写法：

运行时间

解法二：排序搜寻

Java写法：

运行时间

C++写法：

运行时间

时间复杂度和空间复杂度

解法三：看做环

Java写法：

C++写法：

总结

题目链接：287. 寻找重复数 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

给定一个包含 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

示例 3 :

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

提示：

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

进阶：

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

解法一：暴力搜寻

Java写法：

class Solution {public int findDuplicate(int[] nums) {int len = nums.length;int index = 0;while(index < len - 1){for(int i = index + 1; i < len; i++){if(nums[index] == nums[i]){return nums[index];}}index++;}return -1;}
}

运行时间

呃呃呃，嘿嘿,由于这个 $O(n^{2})$ 的时间复杂度，那是过不了了。

解法二：排序搜寻

排序数组：首先对输入数组 nums 进行排序。排序后，重复的元素会相邻出现。
双指针遍历：使用两个指针 p1 和 p2。p1 从数组的第一个元素开始，p2 从第二个元素开始。
查找重复：通过一个 while 循环，检查 p1 和 p2 指向的元素。如果相等，说明找到了重复的数字，返回该数字。
移动指针：如果不相等，则同时将 p1 和 p2 向后移动一位，继续比较。
未找到重复：如果遍历完成后仍未找到重复元素，返回 -1。

当然了，这跟题目的要求是背道而驰的，这里这是提供一种 $O(nlog(n))$ 的解决方法可以跑完测试用例罢了。

Java写法：

class Solution {public int findDuplicate(int[] nums) {Arrays.sort(nums);int p1 = 0;int p2 = 1;while(p2 < nums.length){if(nums[p1] == nums[p2]){return nums[p1];}p1++;p2++;}return -1;}
}

运行时间

C++写法：

#include <vector>
#include <algorithm>class Solution {
public:int findDuplicate(std::vector<int>& nums) {std::sort(nums.begin(), nums.end());int p1 = 0;int p2 = 1;while (p2 < nums.size()) {if (nums[p1] == nums[p2]) {return nums[p1];}p1++;p2++;}return -1;}
};

运行时间

时间复杂度和空间复杂度

解法三：看做环

初始化指针：定义两个指针 slow 和 fast，都初始化为 0。slow 每次移动一步，fast 每次移动两步。
寻找相遇点：使用 do-while 循环，使 slow 和 fast 指针分别根据数组中的值更新位置。当这两个指针相遇时，说明存在环（重复数字），因为在一个包含重复元素的数组中，所有值都可以看作是环的节点。
重置指针：将 slow 重置为 0，然后在第二个 while 循环中，同时移动 slow 和 fast 指针，每次都移动一步。
找到重复数字：当 slow 和 fast 再次相遇时，返回这个值，它就是重复的数字。

Java写法：

class Solution {public int findDuplicate(int[] array) {int turtle = 0, rabbit = 0;// 使用快慢指针寻找相遇点do {turtle = array[turtle];rabbit = array[array[rabbit]];} while (turtle != rabbit);turtle = 0;// 找到重复元素while (turtle != rabbit) {turtle = array[turtle];rabbit = array[rabbit];}return turtle; // 返回重复元素}
}

C++写法：

#include <vector>class Solution {
public:int findDuplicate(std::vector<int>& array) {int turtle = 0, rabbit = 0;// 使用快慢指针寻找相遇点do {turtle = array[turtle];rabbit = array[array[rabbit]];} while (turtle != rabbit);turtle = 0;// 找到重复元素while (turtle != rabbit) {turtle = array[turtle];rabbit = array[rabbit];}return turtle; // 返回重复元素}
};

这种方法的优势在于其空间复杂度为 O(1)，不需要额外的存储空间，同时时间复杂度为 O(n)。