Description
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Example 1:
Input: [1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2]
Output: 3
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, $O(1)$ extra space.
- Your runtime complexity should be less than $O(n^2)$.
- There is only one duplicate number in the array, but it could be repeated more than once.
Solutions
1. 暴力解法
首先,这个问题看起来很简单,不是就找重复的嘛?我直接用 List 或者用 Dict 来找就好了,但是细看规则,这里要求只能用 $O(1)$ 的 Space Complexity。但是我们可以先试下:
# Time Complexity: O(n)
# Space Complexity: O(n)
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dup_list = {}
for item in nums:
if item in dup_list:
return item
else:
dup_list[item] = 1
用 dict 写完后想用 list 也试下,结果发现改成 list 实现会报错 Time Limit Exceeded
。
# Time Complexity: O(n^2)
# Space Complexity: O(n)
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dup_list = []
for item in nums:
if item in dup_list:
return item
else:
dup_list.append(item)
分析了下原因很明显,因为用 list 的 in 来查找,其实就是 $O(n)$ 的时间复杂度啊!
2. 二分查找
我们先找到对应的 mid 值,然后遍历数组中所有的数,统计小于等于 mid 的数的个数,如果个数小于等于 mid,说明重复的数是在 [mid+1, n] 之间,反之在 [1, m-1]。
# Time: O(nlogn)
# Space: O(1)
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
n = len(nums)
l, r = 0, n - 1
while l <= r:
mid = l + ((r - l) >> 1)
cnt = 0
for num in nums:
if num <= mid:
cnt += 1
if cnt <= mid:
l = mid + 1
else:
r = mid - 1
return l
# 53/53 cases passed (76 ms)
# Your runtime beats 28.57 % of python3 submissions
# Your memory usage beats 17.86 % of python3 submissions (15.2 MB)
值得注意的是,除以 2 可以用位操作!
3. 链表有环找入口
接着想办法找到空间复杂度为 $O(1)$ 的方式,看提示说可以将这个问题看成链表中判断是否有环的情况,然后有环的话找对应的环的入口。
[1,3,4,2,2]
0->1->3->2->4->2 cycle: 2->4->2
[3,1,3,4,2]
0->3->4->2->3->4->2 cycle 3->4->2->3
# Time Complexity: O(n)
# Space Complexity: O(1)
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
fast, slow = nums[0], nums[0]
while True:
fast = nums[nums[fast]]
slow = nums[slow]
if fast == slow:
break
fast = nums[0]
while fast != slow:
fast = nums[fast]
slow = nums[slow]
return fast
# Runtime: 68 ms, faster than 98.85% of Python3 online submissions for Find the Duplicate Number.
# Memory Usage: 16.2 MB, less than 7.14% of Python3 online submissions for Find the Duplicate Number.
这种想法的创作动机是什么呢?
4. 位操作
什么骚操作,都没看懂。
# Time Complexity: O(kn)
# Space Complexity: O(1)
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
res, n = 0, len(nums)
MAX_BITS = 32
for i in range(MAX_BITS):
bit, cnt1, cnt2 = 1 << i, 0, 0
for j in range(n):
if j & bit > 0:
cnt1 += 1
if nums[j] & bit > 0:
cnt2 += 1
if cnt2 > cnt1:
res += bit
return res
# Runtime: 216 ms, faster than 5.73% of Python3 online submissions for Find the Duplicate Number.
# Memory Usage: 16.1 MB, less than 7.14% of Python3 online submissions for Find the Duplicate Number.
参考中说对于每一位,0到 n-1 中所有数字中该位上的1的个数应该是固定的,如果 nums 数组中所有数字中该位上1的个数多了,说明重复数字在该位上一定是1,这样我们把重复数字的所有为1的位都累加起来,就可以还原出了这个重复数字。🤔