LeetCode偶尔一题 —— 268. 缺失数字

题目描述

给定一个包含 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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @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)

1
2
3
4
5
6
7
8
/**
* @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/problems/missing-number/
代码不定时更新,欢迎 star 我的 repo