41. First Missing Positive

三刷
swap 之前先check要swap的两个位置是不是一样, 防止infinite loop

100.00 % 
class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) return 1;
        //      [-1,4,3,1]
        //       i
        // index 0 1 2 3
        //       1 2 3 4
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i + 1
                   && nums[i] - 1 >= 0 && nums[i] - 1 < nums.length
                  && nums[i] != nums[nums[i] - 1]) {
                int index = nums[i] - 1;
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}

二刷
用for做感觉edge case太多
debug了很久
因为譬如

[3,4,-1,1]

把4和1swap之后，1就会被换到前面检查过的index从而错过

[1,1]
也是另外一个edge case 会陷入死循环
下面用while 再写一遍[TODO]


15.34 %
class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) return 1;
        int len = nums.length;
        // nums[index] -> value = index + 1
        // [-1,1,3,4]
        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[i] != i + 1) {  // value [1, len]
                int index = nums[i] - 1;
                int temp = nums[index];
                if (temp == nums[i]) break;
                nums[index] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return len + 1;
    }
}

一刷

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

有意思的题，一开始没读懂感觉没法做

它求第一个missing positive integer

譬如 [100, 101, 102]

应该返回1，而不是103

那就容易了

用position的位置代表expected value 就可以了


最后一个else continue是对于有重复的element的情况的处理
譬如[1, 1]
看到一个value去看本来应该放它的位置有没有放对，如果已经放对了就i++ continue，如果没放对就swap

Time O(n) -> 2 pass

Space O(1)

We are using the nums array as the buckets for positive integers

                index         0    1    2  ...     n

expected value         1    2    3  ...     n + 1

If nums[i]'s value is out of the range of our index, then there must be holes in the final array

If it is in the range, we can simply swap it into its desired slot

In the end we scan our array from the start to the end, if there's any slot that the value stored doesn't equals to its index + 1, we know that it is a "hole", which is just the first missing positive integer.

If the array is full, we know that the first n + 1 integers are in place. We can simply return the next integer, which is nums.length + 1.

35.59 %

public class Solution {

    public int firstMissingPositive(int[] nums) {

        if (nums == null || nums.length == 0) return 1;

        int i = 0;

        while (i < nums.length) {

            // If nums[i]  == 1 we want to put it into slot 0

            // nums[i] -> index = nums[i] - 1

            int index = nums[i] - 1;

            if (index < 0 || index >= nums.length) i++;

            else if (nums[index] != nums[i]) {

                swap(nums, i, index);

            } else {

                i++;

            }

            

        }

        for (i = 0; i < nums.length; i++) {

            //System.out.println(i + " " + nums[i]);

            if (i + 1 != nums[i]) return i + 1;

        }

        return nums.length + 1;

        

    }

    private void swap(int[] nums, int i, int j) {

        if (i == j) return;

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

}