First Missing Positive

Description

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

Follow up:

Your algorithm should run in O(n) time and uses constant extra space.

Solution(javascript)

/** 我的这种做法和 Cyclic sort 的对比, 我这里其实就是 Cyclic sort
 * 只不过是用 for 循环搞的，不是那么直观
 * @param {number[]} nums
 * @return {number}
 */
// const firstMissingPositive = (nums = []) => {
//   for (let index = 0; index < nums.length; index++) {
//     while (
//       nums[index] !== nums[nums[index] - 1]
//       && nums[index] >= 1
//       && nums[index] <= nums.length
//     ) {
//       const temp = nums[index]
//       const nextIndex = nums[index] - 1
//       nums[index] = nums[nextIndex]
//       nums[nextIndex] = temp
//     }
//   }
//   for (let i = 0; i < nums.length; i++) {
//     if (nums[i] !== i + 1) {
//       return i + 1
//     }
//   }
//   return nums.length + 1
// }

/** Cyclic sort
 * @param {number[]} nums
 * @return {number}
 */
const firstMissingPositive = (nums = []) => {
  const swap = (a, b) => {
    const temp = nums[a]
    nums[a] = nums[b]
    nums[b] = temp
  }
  let index = 0
  while (index < nums.length) {
    if (
      nums[index] !== nums[nums[index] - 1]
      && nums[index] > 0
      && nums[index] <= nums.length
    ) {
      swap(index, nums[index] - 1)
    } else {
      index += 1
    }
  }
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }
  return nums.length + 1
}