Welcome to Subscribe On Youtube

Question

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

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.

@tag-array

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

Java

• Java
• C++
• Python

• 
  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;
          }
      }
  
  

• // 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
  
  

All Problems

All Solutions