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

Problem

41. First Missing Positive

Proof

首先有如下引理：

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

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

设立两个简单命题，并组成复合命题：

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

简单命题 q:q: ∃b∈[1,a−1],b∉array\exists b \in [1, a-1], b \notin array

复合命题 P:P: p⇒qp \Rightarrow q

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

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

又因为 pp 为真，显然可得 qq 为假，进而 ¬q\neg q 为真。于是 ∀b∈[1,a−1],b∈array\forall b \in [1, a-1], b \in array，引理得证。

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

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

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

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

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

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

所以我们至此就证明了 [1,N+1][1, N+1] 的任何一个元素都可能为解，而 [N+2,∞][N+2, \infty] 都不是解，故解空间为 [1,N+1][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