268 - 缺失数字(missing-number)

Create by jsliang on 2019-07-18 18:10:35
Recently revised in 2019-07-18 18:10:38

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
3.1 解法 - 暴力破解
3.2 解法 - 数学
3.3 解法 - 位运算

二 前言

返回目录

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

示例 1:
输入: [3,0,1]
输出: 2

示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

3.1 解法 - 暴力破解

返回目录

  • 解题代码
var missingNumber = function(nums) {
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i) {
      return i;
    }
    if (nums[i] === i && !nums[i + 1]) {
      return i + 1;
    }
  }
};
  • 执行测试

  • nums[9, 6, 4, 2, 3, 5, 7, 0, 1, 8, 11]

  • return10

  • LeetCode Submit

✔ Accepted
  ✔ 122/122 cases passed (156 ms)
  ✔ Your runtime beats 32.25 % of javascript submissions
  ✔ Your memory usage beats 16.29 % of javascript submissions (37.6 MB)
  • 知识点

  • sort():排序,保持返回数组的数字为顺序排列。sort() 详细介绍

  • 解题思路

首先,因为数组是无序的,所以对数组进行排序。同时,因为 JavaScript 的 sort() 方法,如果你不传参的话,对 [9, 6, 4, 2, 3, 5, 7, 0, 1, 8, 11] 的排序是:

[ 0, 1, 11, 2, 3, 4, 5, 6, 7, 8, 9 ]

所以需要 sort((a, b) => a - b),得出:

[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11 ]

然后,遍历这个数组,index 也是从 0 开始,这个数组也是从 0 开始,所以刚好判断 nums[i] !== i 的时候,我们将 i 给返回出去即可。

当然,LeetCode 还设置了一种情况,即 [0][0, 1][0, 1, 2] 这种,所以我们还需要另外一种判断:

if (nums[i] === i && !nums[i + 1]) {
  return i + 1;
}

最后,我们就通过了这道题。

3.2 解法 - 数学

返回目录

  • 解题代码
var missingNumber = function (nums) {
  let expectedSum = nums.length * (nums.length + 1) / 2;
  let actualSum = nums.reduce((prev, next) => {
    return prev + next;
  });
  return expectedSum - actualSum;
};
  • 执行测试

  • nums[9, 6, 4, 2, 3, 5, 7, 0, 1, 8, 11]

  • return10

  • LeetCode Submit

✔ Accepted
  ✔ 122/122 cases passed (84 ms)
  ✔ Your runtime beats 91.08 % of javascript submissions
  ✔ Your memory usage beats 68.32 % of javascript submissions (36 MB)
  • 知识点

  • reduce()reduce() 方法对数组中的每个元素执行一个由您提供的reducer函数(升序执行),将其结果汇总为单个返回值。reduce() 详细介绍

  • 解题思路

首先,我们需要知道一个公式,叫 高斯求和公式,即:

sum(0, n) === n * (n + 1) / 2

根据 高斯求和公式,我们可以算出 0 - n 的总和。

然后,我们再通过 reduce(),求出这个数组的总和。

最后,这两者的差值,即是缺漏的数字!

  • 进一步思考

如果不希望产生变量,那么,可以缩成一行~

var missingNumber = function (nums) {
  return nums.length * (nums.length + 1) / 2 - nums.reduce((prev, next) => {
    return prev + next;
  });
};

相对的,Submit 变为:

✔ Accepted
  ✔ 122/122 cases passed (84 ms)
  ✔ Your runtime beats 91.08 % of javascript submissions
  ✔ Your memory usage beats 76.02 % of javascript submissions (35.9 MB)

3.3 解法 - 位运算

返回目录

  • 解题代码
var missingNumber = function(nums) {
  let missing = nums.length;
  for (let i = 0; i < nums.length; i++) {
      missing ^= i ^ nums[i];
  }
  return missing;
};
  • 执行测试

  • nums[9, 6, 4, 2, 3, 5, 7, 0, 1, 8, 11]

  • return10

  • LeetCode Submit

✔ Accepted
  ✔ 122/122 cases passed (80 ms)
  ✔ Your runtime beats 95.13 % of javascript submissions
  ✔ Your memory usage beats 39.82 % of javascript submissions (36.6 MB)
  • 解题思路

位运算大法好,只可意会不可言传。

其实 jsliang 也不懂,也不想懂,哈哈~


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-18 19:31:00

results matching ""

    No results matching ""