41.First-Missing-Positive

41. First Missing Positive

题目地址

https://leetcode.com/problems/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.

代码

Approach #1

The key here is to use swapping to keep constant space and also make use of the length of the array, which means there can be at most n positive integers. So each time we encounter an valid integer, find its correct position and swap. Otherwise we continue.

class Solution {
  public int firstMissingPositive(int[] nums) {

    int i = 0, n = nums.length;
    while (i < n) {
    // If the current value is in the range of (0,length) and it's not at its correct position, 
    // swap it to its correct position.
    // Else just continue;
        if (nums[i] >= 0 && nums[i] < n && nums[nums[i]] != nums[i]) {
      swap(nums, i, nums[i]);
    } else {
      i++;
    }
    }
    int k = 1;

    // Check from k=1 to see whether each index and value can be corresponding.
    while (k < n && nums[k] == k) {
    k++;
  }

    // If it breaks because of empty array or reaching the end. K must be the first missing number.
    if (n == 0 || k < n) {
      return k;
    } else {
      // If k is hiding at position 0, K+1 is the number.
      return nums[0] == k ? k + 1 : k;
    }
    }

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

Approach #2 Index as a hash key

Complexity Analysis

• Time complexity : O(N) since all we do here is four walks along the array of length N.

• Space complexity : O(1) since this is a constant space solution.

class Solution {
  public int firstMissingPositive(int[] nums) {
        int n = nums.length;
    int contains = 0;
    for (int i = 0; i < n; i++) {
      if (nums[i] == 1) {
        contains++;
        break;
      }
    }
    if (contains == 0) {
      return 1;
    }

    if (n == 1) {
      return 2;
    }

    for (int i = 0; i < n; i++) {
      if ((nums[i] <= 0) || (nums[i] > n)) {
        nums[i] = 1;
      }
    }

    for (int i = 0; i < n; i++) {
      int a = Math.abs(nums[i]);
      if (a == n) {
        nums[0] = - Math.abs(nums[0]);
      } else {
        nums[a] = - Math.abs(nums[a]);
      }
    }

    for (int i = 1; i < n; i++) {
      if (nums[i] > 0) {
        return i;
      }
    }

    if (nums[0] > 0) {
      return n;
    }

    return n + 1;
  }
}