41. First Missing Positive (1)

Description

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.

Solution:

public int firstMissingPositive(int[] nums) {
    //nums 內容放連續整數，必定是 1 2 3 4 5 最多就是nums.length-1, 所以就從第
    //一個開始swap讓該index的element必定是應該的數字，
    //比方說index 0一定是1, index 1 一定是2 ... etc
    for(int i = 0; i < nums.length; i++){
        //把nums[i]的值 swap到正確的位置 ie. nums[i] - 1
        //要一直轉直到沒法轉(break出去)or已經對了
        while(nums[i] != i+1){
            if(nums[i] > 0 
               && nums[i] <= nums.length 
               && nums[nums[i]-1] != nums[i]){
                    //swap nums[i] and nums[nums[i]-1]
                    //把nums[i]的值 swap到正確的位置 ie. nums[i] - 1
                    int temp = nums[i];
                    nums[i] = nums[temp-1];
                    nums[temp-1] = temp;
            }else{
                break;
            }
        }
    }
    //然後再次檢視nums 若發現哪個位置沒正確的數字，就代表那數字缺乏
    for(int i = 0; i < nums.length; i++){
        if(nums[i] != i+1){
            return i+1;
        }
    }
    return nums.length+1;
}

Set is also working though.

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        
        int i;
        for(i = 1; i <= nums.length ; i++){
            if(!set.contains(i)){
                return i;
            }
        }        
        return i;
    }
}