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.length1 <= n <= 10^40 <= nums[i] <= n- All the numbers of
numsare 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)