跳至主要內容

287. 寻找重复数


287. 寻找重复数open in new window

🟠   🔖  位运算 数组 双指针 二分查找  🔗 力扣open in new window LeetCodeopen in new window

题目

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] 范围内(包括 1n),可知至少存在一个重复的整数。

假设 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(龟兔赛跑) 算法,即通过快慢指针找环。

  1. 理解问题

    • 数组中有 n + 1 个数字,范围是 1n,根据鸽巢原理,至少有一个数字会重复。
  2. 使用快慢指针

    • 将数组视为一个链表,数组的值作为指针指向下一个索引。
    • 使用两个指针:快指针(每次移动两步)和慢指针(每次移动一步)。因为存在重复数字,所以这两个指针最终会在某个节点相遇。
  3. 找出环的起点

    • 首先,使用快慢指针找到相遇点。接着,将其中一个指针移到起点,两个指针同时移动,每次移动一步,直到它们再次相遇。相遇的节点即为重复数字。

复杂度分析

  • 时间复杂度: 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缺失的第一个正数open in new window[✓]数组 哈希表
136只出现一次的数字open in new window[✓]位运算 数组
142环形链表 IIopen in new window[✓]哈希表 链表 双指针
268丢失的数字open in new window[✓]位运算 数组 哈希表 3+
645错误的集合open in new window位运算 数组 哈希表 1+