[Leetcode][268. 丢失的数字] 4种方法：排序，哈希表，异或，数学公式

发表于 更新于 分类于 阅读次数： 本文字数： 3.1k 阅读时长 ≈ 3 分钟

By Long Luo

Leetcode 268. 丢失的数字 ，题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
268. 丢失的数字

给定一个包含[0, n]中n个数的数组nums，找出[0, n]这个范围内没有出现在数组中的那个数。

示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围[0,3]内。2是丢失的数字，因为它没有出现在 nums 中。

示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有2个数字，所以所有的数字都在范围[0,2]内。2是丢失的数字，因为它没有出现在nums中。

示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有9个数字，所以所有的数字都在范围[0,9] 内。8是丢失的数字，因为它没有出现在nums中。

示例 4：
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围[0,1]内。1是丢失的数字，因为它没有出现在 nums 中。
 
提示：
n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
nums 中的所有数字都 独一无二
 
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

方法一：暴力 + 排序

思路与算法

这是一道简单题。首先想到的方法是先进行排序，然后遍历数组，找到值不同的那个数字，如果都相同，那么结果就是lenlen。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
public int missingNumber(int[] nums) {
	int len = nums.length;
	Arrays.sort(nums);
	for (int i = 0; i < len; i++) {
		if (i != nums[i]) {
			return i;
		}
	}

	return len;
}

复杂度分析：

  • 时间复杂度：O(nlog⁡n)O(n \log n)，其中 nn 是数组 nums\textit{nums} 的长度。排序的时间复杂度是 O(nlog⁡n)O(n \log n)，遍历数组寻找丢失的数字的时间复杂度是 O(n)O(n)，因此总时间复杂度是 O(nlog⁡n)O(n \log n)。
  • 空间复杂度：O(log⁡n)O(\log n)，其中 nn 是数组 nums\textit{nums} 的长度。空间复杂度主要取决于排序的递归调用栈空间。

方法二：HashSet

可以使用一个 HashSet\texttt{HashSet} 来记录数组中出现的数，将时间复杂度降低为 O(n)O(n)。

首先遍历数组 nums\textit{nums}，记录数组中的每个元素，然后检查从 00 到 nn 的每个整数是否在哈希集合中，不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是 O(1)O(1)，因此总时间复杂度是 O(n)O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int missingNumber_set(int[] nums) {
	int len = nums.length;
	Set<Integer> set = new HashSet<>();
	for (int i = 0; i < len; i++) {
		set.add(nums[i]);
	}

	for (int i = 0; i <= len; i++) {
		if (set.add(i)) {
			return i;
		}
	}

	return len;
}

复杂度分析：

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

方法三：异或(XOR)

数组 nums\textit{nums} 中有 nn 个数，在这 nn 个数的后面添加从 00 到 nn 的每个整数，则添加了 n+1n+1 个整数，共有 2n+12n+1 个整数。

在 2n+12n+1 个整数中，丢失的数字只在后面 n+1n+1 个整数中出现一次，其余的数字在前面 nn 个整数中（即数组中）和后面 n+1n+1 个整数中各出现一次，即其余的数字都出现了两次。

根据出现的次数的奇偶性，可以使用按位异或运算得到丢失的数字。按位异或运算 ⊕\oplus 满足交换律和结合律，且对任意整数 xx 都满足 x⊕x=0x \oplus x = 0 和 x⊕0=xx \oplus 0 = x。

由于上述 2n+12n+1 个整数中，丢失的数字出现了一次，其余的数字都出现了两次，因此对上述 2n+12n+1 个整数进行按位异或运算，结果即为丢失的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static int missingNumber_xor(int[] nums) {
    int xor = 0;
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        xor ^= nums[i];
    }

    for (int i = 0; i <= len; i++) {
        xor ^= i;
    }

    return xor;
}

复杂度分析：

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(1)O(1)

方法四：数学公式

思路与算法

从 00 到 nn 的全部整数之和记为 total\textit{total}，根据等差数列求和公式，有：

total=∑i=1n=n(n+1)2\textit{total} = \sum_{i=1}^n = \dfrac{n(n+1)}{2}

将数组 nums\textit{nums} 的元素之和记为 arrSum\textit{arrSum}，则 arrSum\textit{arrSum} 比 total\textit{total} 少了丢失的一个数字，因此丢失的数字即为 total\textit{total} 与 arrSum\textit{arrSum} 之差。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
public static int missingNumber_sum(int[] nums) {
    int len = nums.length;
    int sum = len * (len + 1) / 2;
    int arraySum = 0;
    for (int x : nums) {
        arraySum += x;
    }

    return sum - arraySum;
}

复杂度分析：

  • 时间复杂度：O(n)O(n)，其中 nn 是数组 nums\textit{nums} 的长度。需要 O(1)O(1) 的时间计算从 00 到 nn 的全部整数之和以及需要 O(n)O(n) 的时间计算数组 nums\textit{nums} 的元素之和。
  • 空间复杂度：O(1)O(1)。

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗