LeetCode 287. 寻找重复数（二分变形）

Description

给定一个包含 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) 。 数组中只有一个重复的数字，但它可能不止重复出现一次。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-the-duplicate-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

使用hashmap判断是否出现过。

Solution 2

对数组进行排序，相邻两个重复则返回。

Solution 3

自哈希，但是需要修改原始数组。

Solution 4

对1-n的数组二分，每一次二分判断给定数组中<=mid的数字的个数。如果cnt <= mid，则可以排除中位数，待查找的数字在右区间。例如序列1,2,2,3,4,5，当m==3时，<=3的数字理论上有3个(1、2、3)，如果出现4个(1、1、2、3 或者 1、2、2、3 又或者 1、2、2、3)这就说明m的左侧还有重复元素。 使用时间换空间，时间复杂度必然>O(n)。

class Solution: def findDuplicate(self, nums: List[int]) -> int: left = 1 right = len(nums) - 1 while left < right: mid = (left + right) >> 1 cnt = 0 for n in nums: if n <= mid: cnt += 1 if cnt <= mid: left = mid + 1 else: right = mid return left