動機
這題有很多有趣的解法
Problem
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
Example 3:
Input: nums = [1,1]Output: 1
Example 4:
Input: nums = [1,1,2]Output: 1
Constraints:
1 <= n <= 105
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?
Sol
第一個是bsearch
去猜數字
class Solution:
def findDuplicate(self, ns: List[int]) -> int:
a,b = 1, len(ns)+1
while a<b:
mid = (a+b)//2 # 猜數字
cnt, has_num = 0, False
for n in ns:
if n <= mid:
if n == mid:
has_num = True
cnt += 1
if cnt == mid and has_num or cnt < mid:
a = mid+1
elif cnt >= mid:
b = mid
return a
第二個是找loop的起點 (這真的沒想到)
class Solution:
def findDuplicate(self, nums):
# Find the intersection point of the two runners.
tortoise = hare = nums[0]
while True:
tortoise = nums[tortoise]
hare = nums[nums[hare]]
if tortoise == hare:
break
# Find the "entrance" to the cycle.
tortoise = nums[0]
while tortoise != hare:
tortoise = nums[tortoise]
hare = nums[hare]
return hare
第三個是利用1~n的特性把數字放到對應的index上
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
while nums[0] != nums[nums[0]]:
nums[nums[0]], nums[0] = nums[0], nums[nums[0]]
return nums[0]