这个证明思路是昨晚洗澡时想好的,现在写下来。

Problem

41. First Missing Positive

Proof

首先有如下引理:

如果第一个缺失的正数是 a,那么 [1, a-1] 区间上的每一个数一定是数组内的元素。

我们先用反证法证明这个引理。

设立两个简单命题,并组成复合命题:

简单命题 $p:$ 第一个缺失的正数是 a

简单命题 $q:$ $\exists b \in [1, a-1], b \notin array$

复合命题 $P:$ $p \Rightarrow q$

命题 $p$ 是我们的基本设定,值为真,命题 q 是我们要考察的命题,暂时不知道真假。

我们首先假设命题 $P$ 成立,又因为 $p$ 为真,所以推出 $q$ 也为真。又因为 $b \in [1, a-1]$ 即 $b < a$,那么就有 $\left (b < a\right ) \wedge \left (b \notin array\newline\right )$。这说明 b 是一个比 a 更小的缺失正数,换言之 a 不是第一个缺失的正数,这显然与命题 $p$ 为真相矛盾。于是我们的假设不成立,即命题 $P$ 为假。

又因为 $p$ 为真,显然可得 $q$ 为假,进而 $ \neg q $ 为真。于是 $ \forall b \in [1, a-1], b \in array $,引理得证。

有了如上引理,我们就可以尝试证明如下定理:

对于一个含有 N 个元素的数组,此问题的解空间为 [1, N+1]

同样用反证法,先表述一个命题如下。

命题 $p:$ $ \exists c \in [N+2, \infty], c 是解 ( 即 c 是第一个缺失的正数) $

假设 $p$ 为真,则由 $Lemma$ 可得 $ \forall c \in [1, c-1], c \in array $,显然易得区间元素个数 $c-1 \leqslant N$,即 $c \leqslant N + 1$。这显然与命题中 c 的取值区间相矛盾。于是原命题 $p$ 为假,即 $\forall c \in [N+2, \infty], c 不是解$。

那么 N+1 可以是解吗?答案是显然的。只需要让N个元素分别为 $1,2,3,…,N$ 即可。同理可得,$[1, N+1]$ 的任何一个元素都可以成为解。

所以我们至此就证明了 $[1, N+1]$ 的任何一个元素都可能为解,而 $[N+2, \infty]$ 都不是解,故解空间为 $[1, N+1]$。定理得证。

Solution

既然解空间有限,我们就判断一下里面的每个元素在数组里到底存不存在即可。

首先要想个办法能标记出解空间中哪些元素在数组里存在。方法是让数组中每一个元素归位,所谓归位就是让 i == nums[i],对于 i >= n 的元素不做归位。

最后从头扫一遍,没有归位的位置,其下标就是缺失的数字,解空间的数字可能有很多都不在数组里,我们只需找到第一个这样的就是解。注意,nums[0] 可能会藏着数字 n,所以最后要补充判断一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def swap(self, nums, a, b):
nums[a], nums[b] = nums[b], nums[a]

def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
# 归位
i = 0
while i < n:
while nums[i] != i and nums[i] < n and nums[i] >= 0 and nums[nums[i]] != nums[i]:
self.swap(nums, nums[i], i)
i += 1
# 线性扫描寻找未归位的位置
i = 1
while i < n:
if nums[i] == i:
i += 1
continue
else:
return i
# 执行至此说明解空间 [1, n-1] 的数字都在数组中,那只剩 n 和 n+1 这两个可能解了,
# 我们只需判断下 n 有没有藏在 nums[0] 的位置,就能排除出最终解
if nums[0] != n:
return n
else:
return n+1