LeetCode 41 First Missing Positive（丢失的第一個正數）

版權聲明：轉載請聯系本人，感謝配合！本站位址：http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52435582

翻譯

給定一個未排序的整型數組，找出第一個丢失的正數。

例如，

給定 [1,2,0]，傳回 3；

給定 [3,4,−1,1]，傳回 2。

你的算法應該運作在O(n)時間複雜度，并且使用常量空間。

原文

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.

分析

下面是一種偷懶的方法，使用Arrays.sort的複雜度就已經是nlog(n)了。

主要是将其分為以下幾種情況：

• 空數組，傳回1
• 長度為1的數組，元素等于1，傳回2（1的下一個）；不等于1，一律傳回1
• 長度大于等于2的數組，包含元素1：依次周遊，找到第一個為正數，且和下一個數不連續的數，并傳回其下一個數，如果都是連續的，傳回最後一個數的下一個；不包含1，傳回1

public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        if (len < 1) return 1;
        if (len == 1) {
            if (nums[0] == 1)
                return 2;
            else return 1;
        }
        for (int n : nums) {
            if (n == 1) {
                for (int i = 0; i < len -1; i++) {
                    if (nums[i+1] - nums[i] <= 1) {

                    } else if (nums[i] > 0){
                        return nums[i] + 1;
                    }
                }
                return nums[len - 1] + 1;
            }
        }
        return 1;
    }