【Leetcode算法题】268. 丢失的数字

By Long Luo

今天Leetcode的每日一题是:268. 丢失的数字,题目如下:

  1. 丢失的数字

给定一个包含[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}的长度。空间复杂度主要取决于排序的递归调用栈空间。

方法二: 数学

思路与算法:

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
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String getHint(String secret, String guess) {
int len = secret.length();
int bulls = 0;
int cows = 0;
int[] secNums = new int[10];
int[] gusNums = new int[10];
for (int i = 0; i < len; i++) {
int secVal = secret.charAt(i) - '0';
int guessVal = guess.charAt(i) - '0';
secNums[secVal]++;
gusNums[guessVal]++;
if (secVal == guessVal) {
bulls++;
secNums[secVal]--;
gusNums[guessVal]--;
}
}

for (int i = 0; i <= 9; i++) {
cows += Math.min(secNums[i], gusNums[i]);
}

return bulls + "A" + cows + "B";
}

复杂度分析:

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

  • 空间复杂度:O(1)O(1)