41 First Missing Positive

Leetcode

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

要查找的数肯定在数组长度加 1 之内，可以建一个 boolean 数组记录哪些正数访问过，找到第一个没有访问到的。时间复杂度 o(n) ，空间复杂度 o(n)

public int firstMissingPositive(int[] nums) {
    int len=nums.length;
    boolean[] arr=new boolean[len+2];
    for(int i:nums){
        if(i>0 && i<=len) arr[i]=true;
    }
    int ret=1;
    for(;ret<arr.length;++ret){
        if(!arr[ret]) break;
    }
    return ret;
}

这道题是 hard 是因为要写出时间复杂度 o(n) 空间复杂度 o(1) 的解。空间复杂度 o(1) 需要利用原有数组（改变原数组元素），试着尽可能把数组排列成 1 2 3 4 这样的顺序，每个 index 下的值为 index+1 。遍历当前数组。如果某个 index 下的值不为 index+1 ，则尝试把这个值放到正确的位置上，如果这个值不在 1-len 范围内，或是新的位置上已经有正确的值了，就停止。然后找出缺失的正数。

public int firstMissingPositive(int[] nums) {
    int len=nums.length;
    int index=0;
    while(index<len){
        if(nums[index]<=0 && nums[index]>=len) continue;
        while(nums[index]!=index+1){
            int t=nums[index];
            if(t>len || t<=0 || nums[t-1]==t) break;
            nums[index]=nums[t-1];
            nums[t-1]=t;
        }
        index++;
    }
    for(int i=0;i<len;++i){
        if(nums[i]!=i+1) return i+1;
    }
    return len+1;
}