政子的博客

技术|学习|随笔

LeetCode-First Missing Positive

开始的是一个错误案例。。记录在这里是因为如果数字不重复，这个答案肯定满足要求（时间复杂度 O(n)，空间复杂度 O(1)）。

答案中利用的是一串数中缺少的数字是假设它所有数字齐全的和减去它真实的和。

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
27
28
29
func firstMissingPositive(nums []int) int {
    if len(nums)==0 {
        return 1
    }
    min,max,length,sum:=nums[0],nums[0],1,nums[0]
    for i:=1;i<len(nums);i++ {
        n:=nums[i]
        if min<1 || (n>=1 && n<min) {
            min=n
        }
        if n>max {
            max=n
        }
        if n>0 {
            length++
            sum+=n
        }
    }
    if min>1 {
        return 1
    }
    lenDiff:=max-min+1-length
    if lenDiff==0 {
        return max+1
    }
    sumDiff:=(min+max)*(max-min+1)/2-sum
    probMid:=sumDiff/lenDiff
    return probMid-(lenDiff/2-1+lenDiff%2)
}

看了一下 Solution，发现果然我的思路是完全错误的。

这个方法 使用 Python 的非常厉害。不仅丢弃了不用的信息，并且还使用数组的索引作为哈希，并将哈希又存入了数组中！

里面最玄妙的就是 nums[nums[i]%n]+=n 这一行。它将nums[i]中存在的数字的信息存放在了数组中该数字所索引的单元中（为这个单元+n），但是，这个单元本来保有的数字的信息并没有丢失，可以使用对其索引取余进行恢复。所以，在下面检查是否存在某一个数的时候，就直接使用单元中的数字除以其索引，得到的是几，就是该索引代表的数字在整个数组中存在的次数。

简直太厉害了！我认为根本没必要自己再写一遍，作者提供的代码太美妙了！我就直接把作者的代码贴在下面吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def firstMissingPositive(self, nums):
   """
   :type nums: List[int]
   :rtype: int
    Basic idea:
   1. for any array whose length is l, the first missing positive must be in range [1,...,l+1],
       so we only have to care about those elements in this range and remove the rest.
   2. we can use the array index as the hash to restore the frequency of each number within
        the range [1,...,l+1]
   """
   nums.append(0)
   n = len(nums)
   for i in range(len(nums)): #delete those useless elements
       if nums[i]<0 or nums[i]>=n:
           nums[i]=0
   for i in range(len(nums)): #use the index as the hash to record the frequency of each number
       nums[nums[i]%n]+=n
   for i in range(1,len(nums)):
       if nums[i]/n==0:
           return i
   return n

另外一个方法 和上面方法比较类似，是通过将合适的数字放在合适的位置上来做的。

他的做法是让nums[0]=1，nums[1]=2，以此类推，也就是将nums[i]放置在 nums[nums[i]-1]上。

需要主义在判断是否需要 swap 的时候，使用的是A[A[i]-1] != A[i]，而不是A[i]-1 != i，是应为如果数字有重复，那么就会造成无限循环，所以应该套一层A[·]。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int firstMissingPositive(int[] A) {
        int i = 0;
        while(i < A.length){
            if(A[i] == i+1 || A[i] <= 0 || A[i] > A.length) i++;
            else if(A[A[i]-1] != A[i]) swap(A, i, A[i]-1);
            else i++;
        }
        i = 0;
        while(i < A.length && A[i] == i+1) i++;
        return i+1;
    }

    private void swap(int[] A, int i, int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}