缺失的第一个正数

LeetCode每日一题，41.First Missing Positive

先看题目描述

大意就是给定一个没排序的数组，返回最小的缺失的正数

算法和思路

基本思路就是先对数组排序，然后就很好做了，当最小的数字大于 1 时，直接返回 1，当最大的数字小于等于 0 时，也直接返回 1，然后遍历排序后的 nums 数组，当 nums[i - 1] > 0 时，比较 nums[i - 1] 与 nums[i]，若 nums[i] 不等于 nums[i - 1] + 1，返回 nums [i - 1] + 1，当最小的正数大于 1 时，返回 1，若 nums 数组中的正数均连续，就返回最后一个正数 + 1

import java.util.*;

class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums.length == 0) return 1;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0) {
                if (nums[i -  1] <= 0 && nums[i] > 1) return 1;
                if (nums[i-1] > 0 && nums[i] > nums[i - 1] + 1) return nums[i - 1] + 1;
            } else {
                if (nums[i] > 1) return 1;
            }
        }
        if (nums[nums.length - 1] > 0 ) return nums[nums.length - 1] + 1;
        else return 1;
    }
}

后来看了题解发现时间复杂度不符合要求，因为前面有个对数组排序的过程，看题解才知道可以原地哈希

public class Solution {

    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                // 满足在指定范围内、并且没有放在正确的位置上，才交换
                // 例如：数值 3 应该放在索引 2 的位置上
                swap(nums, nums[i] - 1, i);
            }
        }

        // [1, -1, 3, 4]
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        // 都正确则返回数组长度 + 1
        return len + 1;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}