LeetCode 287 Find the Duplicate Number

LeetCode

<div>

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:

<pre>Input: nums = [1,3,4,2,2] Output: 2 </pre>

Example 2:

<pre>Input: nums = [3,1,3,4,2] Output: 3 </pre>

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?

</div>

题目大意：

给定数值范围[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)