268. 丢失的数字

🟢   🔖  位运算 数组 哈希表 数学 二分查找 排序  🔗 力扣 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 的连续整数，可以计算序列的期望和实际和的差值，即缺失的数字。

1. 计算期望和：根据等差数列的求和公式，期望和为 (n * (n + 1)) / 2。
2. 计算实际和：遍历给定的数组，累加得到实际的和。
3. 返回期望和与实际和的差值，即为缺失的数字。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。遍历数组一次。
• 空间复杂度：O(1)，只使用了常数个额外变量。

---

思路二：位运算

在这个思路中，我们可以利用异或运算的性质来解决问题。异或运算有一个很有用的性质：任何数和自身做异或运算结果都为 0。因此，如果我们将数组中的所有数字和它们的索引进行异或运算，那么相同的数字将会互相抵消，最终剩下的结果就是缺失的数字。

1. 初始化一个变量 res，将其赋值为数组的长度 n，因为缺失的数字肯定在 [0, n] 这个范围内。
2. 遍历数组，对 res 和数组元素以及它们的索引进行异或运算。
3. 返回 res，即为缺失的数字。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。遍历数组一次。
• 空间复杂度：O(1)，只使用了常数个额外变量。

---

思路三：负数标记

这个思路的核心思想是利用数组的索引来标记数字的存在。具体步骤如下：

1. 初始化一个长度为 n+1 的布尔数组 arr，初始值为 false。
2. 遍历给定数组 nums，将 arr 中对应的索引位置置为 true。
3. 再次遍历数组 arr，找到第一个值为 false 的索引，该索引即为缺失的数字。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。需要遍历数组两次。
• 空间复杂度：O(n)，需要额外的布尔数组存储数字的存在情况。

---

思路四：压缩状态的负数标记

这个思路在思路三的基础上进行了一些优化。由于题目已经明确说明了数组中的数字范围在 0 到 n 之间，我们可以利用数组中的元素符号来标记数字的存在。具体步骤如下：

1. 遍历数组 nums，将每个元素对应索引位置的元素置为负数，表示该索引对应的数字存在。
2. 再次遍历数组，找到第一个非负数的索引，该索引即为缺失的数字。
3. 如果数组中存在 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	缺失的第一个正数	[✓]	数组 哈希表
136	只出现一次的数字	[✓]	位运算 数组
287	寻找重复数	[✓]	位运算 数组 双指针 1+
765	情侣牵手		贪心 深度优先搜索 广度优先搜索 2+
1980	找出不同的二进制字符串		数组 哈希表 字符串 1+