0041. First Missing Positive

https://leetcode.com/problems/first-missing-positive

Description

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

Constraints:

• 1 <= nums.length <= 5 * 105

• -231 <= nums[i] <= 231 - 1

ac

Array, make use of its indice

class Solution {
    public int firstMissingPositive(int[] nums) {
        // corner case
        if (nums.length == 0) return 1;

        // walk
        for (int i = 0; i < nums.length; i++) {
            // if (nums[i] <= 0 || nums[i] >= nums.length) continue;
            while (nums[i] != i) {
                if (nums[i] <= 0 || nums[i] >= nums.length || nums[nums[i]] == nums[i]) {
                    break;
                } else {
                    int tmp = nums[i];
                    nums[i] = nums[nums[i]];
                    nums[tmp] = tmp;
                }
            }
        }

        // final check
        int res = -1;
        for (int i = 0; i < nums.length; i++) {
            if (i == nums.length - 1 || nums[i+1] != i+1) {
                res = i + 1;
                break;
            }
        }
        res = nums[0] == res ? res + 1 : res; // don't forget nums[0], might equals to result

        // result
        return res;
    }
}

/*
walk
if nums[i] <= 0 or nums[i] >= length, continue
while nums[i] != i swap:
    if nums[nums[i]] == nums[i], nums[nums[i]] = -1
    else swap i, nums[i]

final check: 
    if nums[i+1] != i+1, break, return i+1.

*/

the key is nums[0 and handle duplicate element.

class Solution {
    public int firstMissingPositive(int[] nums) {
        // edge cases
        if (nums == null || nums.length == 0) return 1;

        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i 
                   && nums[i] >= 0 && nums[i] < nums.length 
                   && nums[i] != nums[nums[i]]) {
                int tmp = nums[i];
                nums[i] = nums[tmp];
                nums[tmp] = tmp;
            }
        }

        int i = 1;
        for (; i < nums.length; i++) {
            if (nums[i] != i) return i;
        }

        if (nums[0] == i) i++;

        return i;
    }
}