【寻找重复数字】——脑筋急转弯．．．

寻找重复数字

287. 寻找重复数

题目难度

中等

相关标签与企业信息

[相关标签]
[相关企业]

题目描述

给定一个包含 $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\le n\le 10^5$
• nums.length == n + 1
• $1\le nums[i]\le n$
• nums 中只有一个整数出现两次或多次，其余整数均只出现一次。

进阶问题

如何证明 nums 中至少存在一个重复的数字？

根据抽屉原理（鸽巢原理），将 $n+1$ 个元素放到 $n$ 个集合中，那么至少有一个集合里面会有两个或更多的元素。

在本题中，数组 nums 有 $n+1$ 个整数，而这些整数的取值范围是 $[1,n]$，相当于把 $n+1$ 个“鸽子”放进 $n$ 个“鸽巢”（数字 $1$ 到 $n$ 所代表的 $n$ 个区间），所以必然至少存在一个数字是重复的。

比如一个训练营里面有367人，则必然至少有 两个人生日同一天。

你可以设计一个线性级时间复杂度 $O(n)$ 的解决方案吗？

解题思路

方法一：快慢指针（类似环形链表找环入口）

• 把数组 nums 中的值看作是下一个节点的索引，这样整个数组就可以看作是一个类似链表的结构。
• 由于存在重复的数字，那么必然会形成一个“环”，因为从某个重复数字开始，会再次指向已经访问过的节点（也就是这个重复数字本身对应的下一个节点）。
• 我们可以使用快慢指针的方法来找到这个环的入口，也就是重复的数字。
• 复习链表找环
• 这个也太难想到了吧，没想到这里遇到了环形链表！！

该思路主要是通过将数组视为特殊链表结构来解决寻找重复数的问题，具体如下：

整体思路转化

把给定的数组 nums 中的值当作指向下一个链表节点的索引，从而将寻找数组中重复数字的问题转化为在类似链表结构中寻找环的起点的问题，因为存在重复数字时会形成环。

快慢指针运用

• 初始化：设置 slow 指针指向数组第一个节点（nums[0]），fast 指针指向第二个节点（nums[nums[0]]）。
• 找环过程：通过循环让快慢指针移动，slow 每次按当前节点值作为索引移动一步，fast 每次先根据当前节点值作为索引找到下一个节点，再以该节点值作为索引移动两步。由于 fast 速度是 slow 的两倍，在有环情况下它们必然会在环内相遇。
• 确定重复数：当快慢指针相遇后，设置一个新指针（如代码中的 pre）从链表起点出发，与在环内相遇的 slow 指针同步移动，每次按节点值作为索引前进。由于从链表起点到环入口的距离和从相遇点到环入口的距离相等，所以它们再次相遇的点就是环的入口，即数组中的重复数字。

class Solution:def findDuplicate(self, nums: List[int]) -> int:# 将该数组视为链表，数组上的值视为指向下一个链表节点的索引# 将“寻找数组重复数”的问题转变成了“寻找链表环的起点(已经解决)”# 寻找链表环起点： ## 快慢指针找环## 若相遇，f走了2x，s走了x；假设s在环内走了t，环外链表长x-t，## 此时 head走x-t到入口，s走x-t也回到入口# 初始化快慢指针：slow 第一个节点，fast 第二个节点[第一个节点值作为索引]slow, fast = nums[0], nums[nums[0]]# 判断有无环，while逻辑：没走到终点就一直走# while nums[slow] and !!!这道题不需要判断，默认输入必有环# 所以直接开始找环# 第一次进入环：while slow != fast:slow = nums[slow]fast = nums[nums[fast]]# 退出以上while的条件是实现了s和f指针的第一次相遇# 此时将其中一个指针退回到起点，或者设置一个起点指针pre = 0# 设置pre和s同步走，相遇点就是环入口，就是重复数while pre != slow:slow = nums[slow]pre = nums[pre]return slow

以下是对上述用于寻找数组重复数的代码的时空复杂度分析：

时间复杂度

• 整体分析思路：时间复杂度主要取决于代码中循环语句的执行次数。在这段代码中，有两个主要的 while 循环，我们分别来分析它们对时间复杂度的影响。

• 第一个 while 循环（快慢指针找环）：

  • 在这个循环中，slow 指针和 fast 指针在类似链表的结构中移动，直到它们相遇。由于 fast 指针每次移动的速度是 slow 指针的两倍，所以在最坏的情况下，fast 指针需要绕环两圈才能和 slow 指针相遇（可以想象成在一个环形跑道上，快跑的人要追上慢跑的人，最多跑两圈就能追上）。
  • 而对于整个数组 nums 所构成的类似链表结构，其长度为 n + 1（题目中给定数组包含 n + 1 个整数）。即使在最坏的情况下，fast 指针绕环两圈，它总共走过的节点数也不会超过数组长度的两倍，也就是 O(2(n + 1))，根据大O表示法的特性，常系数可以忽略，所以这个循环的时间复杂度为 O(n)，其中 n 是数组 nums 的长度（准确来说是 n + 1，但在大O表示法中可以近似看作 n）。

• 第二个 while （确定环入口即重复数）：

  • 当快慢指针相遇后，新设置的指针（如代码中的 pre）和在环内相遇的 slow 指针同步移动，直到它们再次相遇找到环的入口，也就是重复的数字。在这个过程中，这两个指针最多需要遍历整个数组长度的节点数，因为从它们开始同步移动到相遇，所走过的路径长度不会超过数组所构成的类似链表结构的总长度。
  • 所以这个循环的时间复杂度同样为 O(n)，其中 n 是数组 nums 的长度。

• 综合时间复杂度：由于整个代码的执行时间主要由这两个 while 循环决定，并且它们的时间复杂度都是 O(n)，所以这段代码的总体时间复杂度为 O(n)。

空间复杂度

• 分析思路：空间复杂度主要看代码在执行过程中额外开辟的空间大小，与输入数据的规模无关。

• 代码中的空间使用情况：在这段代码中，除了定义了几个指针变量（如 slow、fast、pre）来辅助完成算法逻辑外，并没有使用额外的数据结构来存储数据。这些指针变量所占用的空间是固定的，不随输入数组的长度 n 而变化。

• 空间复杂度结论：所以，根据空间复杂度的定义，这段代码的空间复杂度为 O(1)，即只使用了常量级别的额外空间，满足题目要求不使用超过常量级 O(1) 的额外空间来解决问题。

综上所述，这段代码的时间复杂度为 O(n)，空间复杂度为 O(1)。

方法二：二分查找

为什么可以通过 mid（中间值）和 count（小于等于中间值的数字个数）的大小关系来判断重复数字所在的区间。

整体思路

我们的目标是在数组 nums 中找到那个重复的数字，已知数组中的数字范围是 [1, n]，且只有一个数字是重复的。我们通过不断二分这个范围 [1, n]，并根据 count 和 mid 的关系来逐步缩小重复数字可能存在的区间。

具体解释

假设当前我们正在考虑的范围是 [left, right]（在代码中最初就是 [1, len(nums) - 1]，随着循环不断更新 left 和 right），然后我们计算出了这个区间的中间值 mid。

接下来我们统计数组 nums 中小于等于 mid 的数字个数，记为 count。

• 当 count > mid 时：

  • 正常情况下，如果数组中的数字没有重复，那么在范围 [1, mid] 内的数字应该恰好出现 mid 次（因为每个数字只出现一次嘛）。
  • 但现在我们统计出来的 count 大于 mid，这就意味着在 [1, mid] 这个区间内的数字出现的次数比正常情况多了。为什么会多呢？只能是因为那个重复的数字在这个区间内呀，所以重复的数字肯定在 [1, mid] 这个区间，我们就可以把查找范围的上界 right 更新为 mid，下一次就在缩小后的范围 [1, mid] 内继续查找。

• 当 count <= mid 时：

  • 同样，如果数字没有重复，在范围 [1, mid] 内的数字应该恰好出现 mid 次。
  • 现在 count 不大于 mid，说明在 [1, mid] 这个区间内的数字出现的次数是正常的或者更少，那就意味着重复的数字不在这个区间内，而是在 [mid + 1, right] 这个区间里，所以我们就把查找范围的下界 left 更新为 mid + 1，下一次就在缩小后的范围 [mid + 1, right] 内继续查找。

通过这样不断地根据 count 和 mid 的关系来更新查找范围，最终就能确定重复数字所在的区间，当查找范围缩小到只剩下一个数字时，这个数字就是我们要找的重复数字啦。

例如，假设有数组 [3, 1, 3, 4, 2]，我们来模拟一下这个过程：

• 初始时，left = 1，right = 4（因为数组长度是 5，数字范围是 [1, 4]），计算出 mid = 2。
• 统计数组中小于等于 2 的数字个数 count，发现有 2 个（1 和 2），此时 count <= mid，说明重复数字不在 [1, 2] 区间，我们就把 left 更新为 3。
• 下一次循环，left = 3，right = 4，计算出 mid = 3，再统计小于等于 3 的数字个数，发现有 3 个（3，1，2），此时 count > mid，说明重复数字在 [1, 3] 区间，我们就把 right 更新为 3。
• 此时 left = right = 3，所以重复数字就是 3。

希望这样解释能让你清楚理解 mid 和 count 的关系以及为什么可以通过它们来判断重复数字的位置。

！最关键的一步是：mid与count的比较！照理来说，count就是该比mid小！
只要大了，就在这个范围内！

方法二：二分查找

def findDuplicate(nums):low = 1high = len(nums) - 1while low < high:mid = low + (high - low) // 2count = 0for num in nums:if num <= mid:count += 1if count > mid:high = midelse:low = mid + 1return low

测试用例

测试用例1

输入：nums = [1, 3, 4, 2, 2]
预期输出：2

测试用例2

输入：nums = [3, 1, 3, 4, 2]
预期输出：3

测试用例3

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

测试用例4

输入：nums = [1, 2, 3, 4, 4]
预期输出：4

测试用例5

输入：nums = [2, 2, 2, 2, 2]
预期输出：2

测试结果

方法一：快慢指针

• 测试用例1：通过，输出为2。
• 测试用例2：通过，输出为3。
• 测试用例3：通过，输出为3。
• 测试用例4：通过，输出为4。
• 测试用例5：通过，输出为2。

方法二：二分查找

• 测试用例1：通过，输出为2。
• 测试用例2：通过，输出为3。。
• 测试用例3：通过，输出为3。
• 测试用例4：通过，输出为4。
• 测试用例5：通过，输出为2。

通过对多种测试用例的测试，两种方法都能正确地找出数组中重复的数字，满足题目要求。