Question:

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

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

Thinking:

  • Method:
class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < len; i++){
            if(!set.contains(nums[i]))
                set.add(nums[i]);
        }
        int count = 1;
        while(true){
            if(!set.contains(count))
                return count;
            count++;
        }
    }
}

二刷

  1. 首先可以确定返回值是从1 - nums.length + 1;
  2. 将所有元素加入集合，再逐一判断。
class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length == 0) return 1;
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            set.add(nums[i]);
        }
        for(int i = 1; i <= nums.length; i++){
            if(!set.contains(i)) return i;
        }
        return nums.length + 1;
    }
}