41. First Missing Positive

41. First Missing Positive

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

Example 1:

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

Example 2:

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

Example 3:

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

Note:

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

My Solutions：

同268题，448题类似，可以用sort和hashset，但只有方法3：利用index满足 Time: O(n); Space: O(1)

方法3：用数组nums[i]存放（i + 1），从头开始遍历数组，哪个数值没有放在正确的位置（忽略不符合要求的数），将这个数交换到正确的位置（比如对于数字1，数组上index =0的地方应该是1；对于数字2，数组上index=1的地方应该是2）。最后，再从i = 0 开始遍历数组，第一个nums[i] != i + 1的i+1数即为缺失的数据。因为这个位置没有被放置正确过，说明数组中没有这个位置的对应数字。如果都扫完了却一个都没缺，返回数组长度+1（e.g. [1,2] 返回3）

class Solution {
    public int firstMissingPositive(int[] nums) {
        
        if (nums == null) return 0;
        if (nums.length == 0) return 1;
        
        int len = nums.length, ans = 1;
        
        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[i] != nums[nums[i] - 1]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        
        return len + 1;
    }
}

方法1：sort

Time: O(nlgn); Space: O(1)

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

方法2：hashset

Time: O(n); Space: O(n)

public class Solution {
    public int firstMissingPositive(int[] A) {
        int miss = A.length + 1;
        
        HashSet<Integer> hashset = new HashSet<Integer>();
        for (int i = 0; i < A.length; i ++) {
            hashset.add(A[i]);
        }
        
        for (int i = 1; i <= A.length; i ++) {
            if (!hashset.contains(i)) {
                miss = i;
                break;
            }
        }
        return miss;
    }