287. 寻找重复数
287. 寻找重复数
🟠 🔖 位运算
数组
双指针
二分查找
🔗 力扣
LeetCode
题目
Given an array of integers nums
containing n + 1
integers where each integer is in the range [1, n]
inclusive.
There is only one repeated number in nums
, return this repeated number.
You must solve the problem without modifying the array nums
and using only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
Example 3:
Input: nums = [3,3,3,3,3]
Output: 3
Constraints:
1 <= n <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
- All the integers in
nums
appear only once except for precisely one integer which appears two or more times.
Follow up:
- How can we prove that at least one duplicate number must exist in
nums
? - Can you solve the problem in linear runtime complexity?
题目大意
给定一个包含 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 <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
nums
中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次
进阶:
- 如何证明
nums
中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度
O(n)
的解决方案吗?
解题思路
这道题可以使用 Floyd's Tortoise and Hare(龟兔赛跑) 算法,即通过快慢指针找环。
理解问题:
- 数组中有
n + 1
个数字,范围是1
到n
,根据鸽巢原理,至少有一个数字会重复。
- 数组中有
使用快慢指针:
- 将数组视为一个链表,数组的值作为指针指向下一个索引。
- 使用两个指针:快指针(每次移动两步)和慢指针(每次移动一步)。因为存在重复数字,所以这两个指针最终会在某个节点相遇。
找出环的起点:
- 首先,使用快慢指针找到相遇点。接着,将其中一个指针移到起点,两个指针同时移动,每次移动一步,直到它们再次相遇。相遇的节点即为重复数字。
复杂度分析
- 时间复杂度:
O(n)
,在最坏情况下,快慢指针的移动次数不会超过n
次。 - 空间复杂度:
O(1)
,只使用了常量的空间,不需要额外的数据结构。
代码
/**
* @param {number[]} nums
* @return {number}
*/
var findDuplicate = function (nums) {
let slow = nums[0],
fast = nums[0];
// 找到环的交点
do {
slow = nums[slow]; // 走一步
fast = nums[nums[fast]]; // 走两步
} while (slow !== fast);
// 找出循环的起始点(即重复的数字)
fast = nums[0];
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
41 | 缺失的第一个正数 | [✓] | 数组 哈希表 | |
136 | 只出现一次的数字 | [✓] | 位运算 数组 | |
142 | 环形链表 II | [✓] | 哈希表 链表 双指针 | |
268 | 丢失的数字 | [✓] | 位运算 数组 哈希表 3+ | |
645 | 错误的集合 | 位运算 数组 哈希表 1+ |