[LeetCode：Missing Number] | 刷题打卡

题目描述

给你一个只包括 [0,n] 数字的数组，返回丢失的哪个唯一的数字，n 是数组的长度

例一：

输入: nums = [3,0,1]
输出: 2
解释: 数组长度为 3，所以 n === 3, 正常的序列应该是 [0,1,2,3]，丢失的是 2

例二：

输入: nums = [0,1]
输出: 2
解释: n === 2, 正常的序列是 [0,1,2], 所以，丢失的是 2

例二：

输入: nums = [0,1]
输出: 2
解释: n === 2, 正常的序列是 [0,1,2], 所以，丢失的是 2

例三：

输入: nums = [9,6,4,2,3,5,7,0,1]
输出: 8
Explanation: n === 9, 正常的序列是 [0,1,2,3,4,5,6,7,8,9], 所以，丢失的是 8 

例四：

输入: nums = [0]
输出: 1
解释: n === 1, 正常的序列是 [0,1], 所以，丢失的是 1

思路分析

先分析样例的特点：

1. nums 中的数字都是自然数
2. nums 中数字可能乱序
3. nums 中数字少了一个，可能是中间的数，也可能是边界的数

一种想法是先把数字排序，有序的数组找丢失的数会方便很多，但是排序的平均时间复杂度都是 O(nlogn)，不能接受。

第二种想法是：申请一个长度等于 nums 的数组 arr，由于 nums 中的数字都是自然数，刚好和数组的下标对应，遍历到 nums[k] 的时候，在 arr[nums[k]] 标记一下，最后遍历 arr 就知道缺失的是哪个数，但是需要 O(n) 的空间复杂度。

有没有办法可以时间复杂度为 O(n)，空间复杂度能为 O(1) 呢？

这个时候就祭出我们学前班就学过的数学知识（致敬毕导）：等差数列的前 n 项和

nums 的长度为 n

那么：$Sn=\frac{(1+n)\ast n}{2}$Sn=2(1+n)∗n​

遍历的时候不断用 Sn 的值减当前遍历的值，最后剩下的值就是缺失的值

AC 代码

var missingNumber = function (nums) {
  let sum = ((1 + nums.length) * nums.length) / 2;
  let i = 0;
  while (i < nums.length) {
    sum -= nums[i];
    i++;
  }
  return sum;
};

总结

写算法的时候用上数学知识会有奇效~

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情