268.丢失的数字.md

268.丢失的数字

/*
 * @lc app=leetcode.cn id=268 lang=typescript
 *
 * [268] 丢失的数字
 */

// @lc code=start
function missingNumber(nums: number[]): number {}
// @lc code=end

解法 1: 累加求和

• 时间复杂度:
• 空间复杂度:

根据题意可知 nums 数组和 0n 就差一个数,那我们可以通过将 0n 和 nums 数组中的数分别相加,取其差既为差的那个数

function missingNumber(nums: number[]): number {
  let sum = nums.length
  for (let i = 0; i < nums.length; i++) {
    sum += i - nums[i]
  }
  return sum
}

解法 2: 位运算

• 时间复杂度:
• 空间复杂度:

利用异或运算的特性

function missingNumber(nums: number[]): number {
  let num = nums.length
  for (let i = 0; i < nums.length; i++) {
    num ^= i ^ nums[i]
  }
  return num
}

解法 3: 哈希表

• 时间复杂度:
• 空间复杂度:

使用一个哈希表去保存所有数,然后遍历 0~n 查看哪个数是不存在的

function missingNumber(nums: number[]): number {
  const cache = new Set(nums)
  for (let i = 0; i <= cache.size; i++) {
    if (!cache.has(i)) return i
  }
}

解法 4: 排序

• 时间复杂度:
• 空间复杂度:

根据题意,当没有缺少数字的情况下,则每个数跟其索引是一一对应相等的,而缺少之后,则在缺少的位置,其索引不等于对应的数字,这个索引就是缺少的数字

function missingNumber(nums: number[]): number {
  const arr = [...nums].sort((a, b) => a - b)
  for (let i = 0; i <= arr.length; i++) {
    if (i !== arr[i]) return i
  }
}

Case

test.each([
  { input: { nums: [3, 0, 1] }, output: 2 },
  { input: { nums: [0, 1] }, output: 2 },
  { input: { nums: [9, 6, 4, 2, 3, 5, 7, 0, 1] }, output: 8 },
  { input: { nums: [0] }, output: 1 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(missingNumber(nums)).toBe(output)
})