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

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(nlogn)O(n \log n),其中 nn 是数组 nums\textit{nums} 的长度。排序的时间复杂度是 O(nlogn)O(n \log n),遍历数组寻找丢失的数字的时间复杂度是 O(n)O(n),因此总时间复杂度是 O(nlogn)O(n \log n)
  • 空间复杂度:O(logn)O(\log n),其中 nn 是数组 nums\textit{nums} 的长度。空间复杂度主要取决于排序的递归调用栈空间。

方法二:HashSet

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

首先遍历数组 nums\textit{nums},记录数组中的每个元素,然后检查从 00nn 的每个整数是否在哈希集合中,不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是 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 个数的后面添加从 00nn 的每个整数,则添加了 n+1n+1 个整数,共有 2n+12n+1 个整数。

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

根据出现的次数的奇偶性,可以使用按位异或运算得到丢失的数字。按位异或运算 \oplus 满足交换律和结合律,且对任意整数 xx 都满足 xx=0x \oplus x = 0x0=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)

方法四:数学公式

思路与算法

00nn 的全部整数之和记为 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) 的时间计算从 00nn 的全部整数之和以及需要 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. 😉😃💗