Question

Formatted question description: https://leetcode.ca/all/41.html

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
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

Algorithm

Put 1 in the first position nums[0] of the array and 2 in the second position nums[1], that is, you need to put nums[i] on nums[nums[i]-1] to traverse the entire array,

If nums[i] != i + 1, and nums[i] is an integer and is not greater than n, and nums[i] is not equal to nums[nums[i]-1], swap the two positions,
if not satisfied above conditions are skipped directly, and the array is traversed again. If the number at the corresponding position is incorrect, the correct number will be returned.

Note

The key is to deal with the collision. If there are repeated numbers 1, 1, or 2, 2. If the collision means that there is the correct number at the correct position, ++ will go to the next one.

Code

import java.util.Arrays;

public class First_Missing_Positive {

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

	        // two pointers, in plcace sort
	        int i = 0;
	        while (i < nums.length) {

                while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                    // put nums[i] to index nums[i]-1
                    int digit = nums[i];
                    int swapIndex = digit - 1;

                    int tmp = nums[swapIndex];
                    nums[swapIndex] = digit;
                    nums[i] = tmp;
                }

                i++;
            }

            // another scan for the missing one
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] != j + 1) {
                    return j + 1;
                }
            }

            // @note: case for [1,2,3,4,5]
            return nums.length + 1;
        }
    }


############

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (i + 1 != nums[i]) {
                return i + 1;
            }
        }
        return n + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

// OJ: https://leetcode.com/problems/first-missing-positive/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int firstMissingPositive(vector<int>& A) {
        int i, N = A.size();
        for (i = 0; i < N; ) {
            if (A[i] == i + 1 || A[i] < 1 || A[i] >= N + 1 || A[i] == A[A[i] - 1]) ++i;
            else swap(A[i], A[A[i] - 1]);
        }
        for (i = 0; i < N && A[i] == i + 1; ++i);
        return i + 1;
    }
};

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]

        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                swap(i, nums[i] - 1)
        for i in range(n):
            if i + 1 != nums[i]:
                return i + 1
        return n + 1

############

class Solution(object):
  def firstMissingPositive(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    i = 0
    while i < len(nums):
      if 0 < nums[i] <= len(nums) and nums[nums[i] - 1] != nums[i]:
        nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
      else:
        i += 1

    for i in range(0, len(nums)):
      if nums[i] != i + 1:
        return i + 1
    return len(nums) + 1

func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := range nums {
		for nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i]-1] {
			nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
		}
	}
	for i, v := range nums {
		if i+1 != v {
			return i + 1
		}
	}
	return n + 1
}

function firstMissingPositive(nums: number[]): number {
    const n = nums.length;
    let i = 0;
    while (i < n) {
        const j = nums[i] - 1;
        if (j === i || j < 0 || j >= n || nums[i] === nums[j]) {
            i++;
        } else {
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
    }

    const res = nums.findIndex((v, i) => v !== i + 1);
    return (res === -1 ? n : res) + 1;
}

public class Solution {
    public int FirstMissingPositive(int[] nums) {
        var i = 0;
        while (i < nums.Length)
        {
            if (nums[i] > 0 && nums[i] <= nums.Length)
            {
                var index = nums[i] -1;
                if (index != i && nums[index] != nums[i])
                {
                    var temp = nums[i];
                    nums[i] = nums[index];
                    nums[index] = temp;
                }
                else
                {
                    ++i;
                }
            }
            else
            {
                ++i;
            }
        }

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

impl Solution {
    pub fn first_missing_positive(mut nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut i = 0;
        while i < n {
            let j = nums[i] - 1;
            if i as i32 == j || j < 0 || j >= n as i32 || nums[i] == nums[j as usize] {
                i += 1;
            } else {
                nums.swap(i, j as usize);
            }
        }
        nums.iter()
            .enumerate()
            .position(|(i, &v)| v as usize != i + 1)
            .unwrap_or(n) as i32
            + 1
    }
}

41 - First Missing Positive

Question

Algorithm

Note

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Note

Code

All Problems

All Solutions