LeetCode -- 287

本文讨论LeetCode 287

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:

1
2
Input: [1,3,4,2,2]
Output: 2

Example 2:

1
2
Input: [3,1,3,4,2]
Output: 3

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, $O(1)$ extra space.
  3. Your runtime complexity should be less than $O(n^2)$.
  4. There is only one duplicate number in the array, but it could be repeated more than once.

Solution

简要概括题意:$n+1$大小的数组$nums$,其中元素都是$1\sim n$,并且有且仅有一个数字重复出现,找到这个数字。要求$O(1)空间$。

直观来看并没有什么思路,这题的题眼是元素属于$[1,n]$。

如果把每个数字看作一个node,对于$(i, nums[i])$,连一条有向边$i\rightarrow nums[i]$。那么以下结论显然成立:

  1. 只有一个节点的入度大于$1$(只有一个数字重复出现);
  2. 图中一定存在一个环(数组大小$n+1$)。

那么问题就变成了:找到这个环的起点。

如何找到一个环的起点,这个问题在LeetCode 142中有详细解答,也可参照我的博客

Python Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
def Next(p):
return nums[p]

p = Next(0)
q = Next(Next(0))
while p != q:
p = Next(p)
q = Next(Next(q))

q = 0
while p != q:
p, q = Next(p), Next(q)

return p
------ 本文结束------
0%