社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
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 解法 - 位运算 |
难度:简单
涉及知识:位运算、数组、数学
题目地址:https://leetcode-cn.com/problems/missing-number/
题目内容:
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。
解题代码:
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]
return
: 10
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;
}
最后,我们就通过了这道题。
解题代码:
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]
return
: 10
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)
解题代码:
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]
return
: 10
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/ 处获得。
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!