287. Find the Duplicate Number
Medium
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 <= 105nums.length == n + 11 <= nums[i] <= n- All the integers in
numsappear 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?
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# using sort
nums.sort()
prev = nums[0]
for num in nums[1:]:
if prev == num:
return num
prev = num
# negative marking
# for num in nums:
# cur = abs(num)
# if nums[cur] < 0:
# duplicate = cur
# break
# nums[cur] = -nums[cur]
# # Restoring numbers
# for i in range(len(nums)):
# nums[i] = abs(nums[i])
# return duplicate
# using set
# s = set()
# for num in nums:
# if num in s:
# return num
# else:
# s.add(num)
# using Binary search
# # 'low' and 'high' represent the range of values of the target
# low = 1
# high = len(nums) - 1
# while low <= high:
# cur = (low + high) // 2
# count = 0
# # Count how many numbers are less than or equal to 'cur'
# count = sum(num <= cur for num in nums)
# if count > cur:
# duplicate = cur
# high = cur - 1
# else:
# low = cur + 1
# return duplicate