268. Missing Number
268. Missing Number
🟢 🔖 位运算
数组
哈希表
数学
二分查找
排序
🔗 LeetCode
题目
Given an array nums
containing n
distinct numbers in the range [0, n]
, return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.
Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.
Constraints:
n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
- All the numbers of
nums
are unique.
Follow up: Could you implement a solution using only O(1)
extra space complexity and O(n)
runtime complexity?
题目大意
给定一个包含 [0, n]
中 n
个数的数组 nums
,找出 [0, n]
这个范围内没有出现在数组中的那个数。nums
中的所有数字都 独一无二。
解题思路
思路一:数学运算
这个问题可以通过数学运算来解决。由于序列包含的是从 0
到 n
的连续整数,可以计算序列的期望和实际和的差值,即缺失的数字。
- 计算期望和:根据等差数列的求和公式,期望和为
(n * (n + 1)) / 2
。 - 计算实际和:遍历给定的数组,累加得到实际的和。
- 返回期望和与实际和的差值,即为缺失的数字。
- 时间复杂度:
O(n)
,其中n
是数组的长度。遍历数组一次。 - 空间复杂度:
O(1)
,只使用了常数个额外变量。
思路二:位运算
在这个思路中,我们可以利用异或运算的性质来解决问题。异或运算有一个很有用的性质:任何数和自身做异或运算结果都为 0。因此,如果我们将数组中的所有数字和它们的索引进行异或运算,那么相同的数字将会互相抵消,最终剩下的结果就是缺失的数字。
- 初始化一个变量
res
,将其赋值为数组的长度n
,因为缺失的数字肯定在[0, n]
这个范围内。 - 遍历数组,对
res
和数组元素以及它们的索引进行异或运算。 - 返回
res
,即为缺失的数字。
- 时间复杂度:
O(n)
,其中n
是数组的长度。遍历数组一次。 - 空间复杂度:
O(1)
,只使用了常数个额外变量。
思路三:负数标记
这个思路的核心思想是利用数组的索引来标记数字的存在。具体步骤如下:
- 初始化一个长度为
n+1
的布尔数组arr
,初始值为false
。 - 遍历给定数组
nums
,将arr
中对应的索引位置置为true
。 - 再次遍历数组
arr
,找到第一个值为false
的索引,该索引即为缺失的数字。
- 时间复杂度:
O(n)
,其中n
是数组的长度。需要遍历数组两次。 - 空间复杂度:
O(n)
,需要额外的布尔数组存储数字的存在情况。
思路四:压缩状态的负数标记
这个思路在思路三的基础上进行了一些优化。由于题目已经明确说明了数组中的数字范围在 0
到 n
之间,我们可以利用数组中的元素符号来标记数字的存在。具体步骤如下:
- 遍历数组
nums
,将每个元素对应索引位置的元素置为负数,表示该索引对应的数字存在。 - 再次遍历数组,找到第一个非负数的索引,该索引即为缺失的数字。
- 如果数组中存在
0
,则标记下来,因为0
在这种方法下无法通过负数标记。
- 时间复杂度:
O(n)
,其中n
是数组的长度。需要遍历数组两次。 - 空间复杂度:
O(1)
,只使用了常数个额外变量。
代码
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function (nums) {
const n = nums.length;
const expect = (n * (n + 1)) / 2;
const sum = nums.reduce((acc, num) => acc + num, 0);
return expect - sum;
};
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function (nums) {
const n = nums.length;
let res = n;
for (let i = 0; i < n; i++) {
res ^= nums[i] ^ i;
}
return res;
};
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function (nums) {
const n = nums.length;
let arr = new Array(n + 1).fill(false);
for (let i = 0; i < n; i++) {
arr[nums[i]] = true;
}
let res;
for (let i = 0; i <= n; i++) {
if (!arr[i]) {
res = i;
break;
}
}
return res;
};
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function (nums) {
let res, res_0;
const n = nums.length;
for (let i = 0; i < n; i++) {
let index = Math.abs(nums[i]);
if (index == n) {
nums[index] = -n;
} else {
nums[index] = -nums[index];
}
}
for (let i = 0; i <= n; i++) {
if (nums[i] > 0 || nums[i] == undefined) {
res = i;
break;
}
if (nums[i] == 0) {
res_0 = i;
}
}
return res == undefined ? res_0 : res;
};
相关题目
- [41. 缺失的第一个正数](./0041.md)
- [136. 只出现一次的数字](./0136.md)
- [287. 寻找重复数](https://leetcode.com/problems/find-the-duplicate-number)
- [765. 情侣牵手](https://leetcode.com/problems/couples-holding-hands)
- [1980. 找出不同的二进制字符串](https://leetcode.com/problems/find-unique-binary-string)