题目描述
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
最简单的解法
刚看到的这道题的时候，第一感觉就是排序，之后直接挨个比较就能找到缺失的数字。
时间复杂度 ：O(nlog(n))， 空间复杂度：O(1)
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
let i = 0
nums.sort((a, b) => a - b)
for (i = 0; i < nums.length; i++) {if (i !== nums[i]) {return i}
}
return i
};写完之后感觉不用排序也行，可以开辟新的数组来做标记。时间复杂度 ：O(n)， 空间复杂度：O(n)
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {let i = 0, tmp = []
for (i = 0; i < nums.length + 1; i++) {tmp[i] = true
}
for (i = 0; i < nums.length; i++) {if (tmp[nums[i]]) {tmp[nums[i]] = false
}
}
return tmp.indexOf(true)
};进阶
其实细心的人可以发现，数组是不含重复数字的，也就是说我们可以将这道题转化为 等差数列的前 n 项和 与 该数组 的差。 时间复杂度 ：O(n), 空间复杂度：O(1)
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {let n = nums.length, sum = (1 + n) * n / 2
return sum - nums.reduce((cur, next) => cur + next)
};当然，这道题也可以用 异或 来求解，感兴趣的朋友可以戳下面的链接查看。
原题地址: https://leetcode-cn.com/probl…
代码不定时更新，欢迎 star 我的 repo
扫描下方的二维码或搜索「tony 老师的前端补习班」关注我的微信公众号，那么就可以第一时间收到我的最新文章。