首页 > 代码库 > 【LeetCode】First Missing Positive 解题报告

【LeetCode】First Missing Positive 解题报告

【题目】

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

【解析】

题意:给定一个数组,找出第一个缺失的正数,要求时间复杂度为O(n),空间复杂度为O(1)。

这道题为LeetCode上的一道Hard类型的题,第一次看没想出来怎么做,放了两天,然后某个空当突然就想到了解题思路:

public class Solution {
    public int firstMissingPositive(int[] A) {
        if (A == null || A.length < 1) return 1;
        
        //求数组中正数的个数cnt
        int cnt = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0) {
                cnt++;
            }
        }
        
        //用一个数组标记从0到cnt的正数是否出现过
        boolean[] flag = new boolean[cnt + 1];
        Arrays.fill(flag, false);
        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0 && A[i] <= cnt) {
                flag[A[i]] = true;
            }
        }
        
        //从0到cnt第一个没有出现的正数就是要返回的结果
        for (int i = 1; i <= cnt; i++) {
            if (!flag[i]) return i;
        }
        
        return cnt + 1;
    }
}


===白高兴一场,上面解法好像不是O(1)===

正确解法如下,把正数n放在第n-1个位置上,这样从第一个位置开始,如果位置上的数不等于位置号,那么就是第一个缺失的正数:

public class Solution {
    public int firstMissingPositive(int[] A) {
        if (A == null || A.length < 1) return 1;
        
        //把小于等于A.length的正数A[i]放到第A[i]-1个位置上
        for (int i = 0; i < A.length; i++) {
            while (A[i] > 0 && A[i] <= A.length && A[A[i] - 1] != A[i]) {
                int tmp = A[A[i] - 1];
                A[A[i] - 1] = A[i];
                A[i] = tmp;
            }
        }
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i + 1) {
                return i + 1;
            }
        }
        
        return A.length + 1;
    }
}


【LeetCode】First Missing Positive 解题报告