8. Find Missing positive integer

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.

For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.

You can modify the input array in-place.

41. First Missing Positive

• Sort - O(nlogn)

  • iterate over the sorted array and return the first number that doesn't match the index

• Set - O(n), space O(n)

def first_missing_positive(nums):
      s = set(nums)
    i = 1
    while i in s:
      i+= 1
    return i

def first_missing_positive(nums):
  if not nums:
    return 1

  for i, num in enumerate(nums):
    # key:  positive number must be between 1 and len(array) + 1 (why?)
    # [1,2,3,4,6] <-- index4應該要上5的
    # while loop的目的，交換後的i的位置，可能又是其他的數字，繼續的再換出去
    # 當只有大於0的數字才進行交換
    while nums[i] != i + 1 and 0 < nums[i] <= len(nums):
      v = nums[i] 
      # v這個數字，要放在array v-1這個index上
      # 把正確數字放到正確的index上(ex. 5要放到index4上)
      nums[i], nums[v - 1] = nums[v - 1], nums[i]
      # 交換後的數字很幸運在正確的index上
      if nums[i] == nums[v - 1]:
        break

  print(nums) # [1, -1, 3, 4]
  for i, num in enumerate(nums, 1):
    print(str(i) + " -- " + str(num))
    # 1 -- 1
    # 2 -- -1
    if num != i:
      return i

  # [1,2,3,4,5] <-- 剛好排滿整個array 
  return len(nums) + 1