Missing Number

Description

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Solution(javascript)

/** 高斯公式
 * @param {number[]} nums
 * @return {number}
 */
const missingNumber = (nums = []) => {
  let min = Infinity
  let max = -Infinity
  let sum = 0

  nums.forEach((num) => {
    min = Math.min(num, min)
    max = Math.max(num, max)
    sum += num
  })
  const result = (nums.length) * (nums.length + 1) / 2 - sum

  return result
}

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