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.

Solution

(1) Java

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (num == 0) {
                continue;
            }
            if (num > nums.length || num < 0) {
                nums[i] = 0;
            } else if (num == i+1) {
                continue;
            }else {
                nums[i] = 0;
                while (true) {
                    int tmp = nums[num-1];
                    if (tmp == num) {
                        break;
                    }
                    nums[num-1] = num;
                    if (tmp <= 0 || tmp > nums.length) {
                        break;
                    } else {
                        num = tmp;
                    }
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                return i+1;
            }
        }
        return nums.length+1;
    }
}

(2) Python

class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 1
        for i in range(len(nums)):
            num = nums[i]
            while num > 0 and num <= len(nums) and nums[num-1] != num:
                tmp = nums[num-1]
                nums[num-1] = num
                num = tmp
        for i in range(len(nums)):
            if nums[i] != i+1:
                return i+1
        return len(nums)+1

(3) Scala