287. 寻找重复数
题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/find-the-duplicate-number
题目
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
- 不能更改原数组（假设数组是只读的）。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n2) 。
- 数组中只有一个重复的数字，但它可能不止重复出现一次。
解题思路
思路：二分查找
这里需要注意，题意中说明，有 4 个提示。这里会限制一些方法，例如：
- 对数组排序，重复数相邻，根据这个就可以找到重复数（这里违背【不能更改原数组】）
- 使用哈希表，（这里违背【只能使用额外的 O(1) 算法】）
- ...
上面的方法，在没有限制的情况下，可以使用，但是在这里，由于题目给出了限制，所以暂不考虑。
先看本题，【给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n）】，这是题目中给定的前提。
根据这个前提，这里二分法的思路是先定一个数值（这里同样定 [left, right] 的中间值 mid），不过这里要统计的是原始数组中，小于等于这个 mid 的值的元素个数（这里定义为 count）。如果这个 count 严格大于 mid 的值的话，这个重复元素就会落在区间 [left, mid] 中。
这里涉及一个原理：抽屉原理。关于 抽屉原理，大致是这样的一个现象：如果桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。
以题目中所给的示例 1 进行展开分析：
[1,3,4,2,2]
首先，我们知道，这里的数值 2 是重复值。现在，我们按照上面的思路来分析一下。
这里有 5 个数字，即是 n + 1 = 5，n = 4，那么这里数组的数值都在 1 到 4 之间。
现在先定一个值（根据上面所述的中间值 mid），这里定为 2，遍历数组，统计小于等于 2 的数字个数。这里可以看到，有 3 个值，严格大于 mid，所以重复值落在 [1, 2] 这个区间中。
具体的代码实现如下。
代码实现
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
size = len(nums)
left = 1
right = size - 1
while left < right:
# 先找中间值
mid = left + (right - left) // 2
# mid = (left + right) // 2
# 遍历数组
# 统计数组中小于等于中间值的元素个数
count = 0
for num in nums:
if num <= mid:
count += 1
# 如果统计数严格大于中间值时，那么重复值将落在 [left, mid] 这个区间
if count > mid:
# 将右边界缩小到 mid
right = mid
# 否则重复值落在 [mid + 1, right]
else:
left = mid + 1
return left
实现结果
实现结果
总结
- 根据题意给定的前提，使用二分查找的思路，先找一个中间值 mid（在区间 [left, right] 中找）。
- 统计原数组中小于等于中间值 mid 的个数 count，当 count 严格大于 mid 时，那么这个重复数值会落在 [left, mid] 区间中
欢迎关注微信公众号《书所集录》
网友评论