LeetCode 287 Find the Duplicate Number

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 uses 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

Constraints:

1 <= n <= 10<sup>5</sup> 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?

题目大意：

给定数值范围[1, n]找重复的数，只有一个重复数，但可能重复多次。题目要求不能用额外空间，不能修改数组

解题思路：

数值二分法

解题步骤：

N/A

注意事项：

1. 比较mid和count的关系，用例子来写程序，如[1, 2, 2, 3, 4]
2. 重复的数可能重复多次，所以不能用异或法

Python代码：

def findDuplicate(self, nums: List[int]) -> int:
	start, end, epsilon = min(nums), max(nums), 0.5
	while end - start > epsilon:
		mid = start + (end - start) / 2
		count = len([n for n in nums if n <= mid])
		if count <= mid:
			start = mid
		else:
			end = mid
	return int(end)

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(1)