消失的数字
难度:
标签:
题目描述
An array contains all the integers from 0 to n, except for one number which is missing. Write code to find the missing integer. Can you do it in O(n) time?
Note: This problem is slightly different from the original one the book.
Example 1:
Input: [3,0,1] Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1] Output: 8
代码结果
运行时间: 25 ms, 内存: 17.0 MB
/*
* 思路：
* 使用Java Stream API简化代码。
* 我们可以通过计算从0到n的整数之和，并减去数组中所有整数的和，得到缺失的整数。
* 这种方法的时间复杂度是O(n)。
*/
import java.util.Arrays;
public class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
// 计算从0到n的整数之和
int expectedSum = n * (n + 1) / 2;
// 使用Stream计算数组中所有整数的和
int actualSum = Arrays.stream(nums).sum();
// 缺失的整数等于expectedSum减去actualSum
return expectedSum - actualSum;
}
}解释
方法:
题解的思路基于高斯求和公式。对于给定的n，从0到n的所有整数的和可以通过公式 S = n * (n + 1) / 2 计算出来。这个公式得到的是如果没有缺失数字时，数组应该有的总和。题解中通过计算这个理论上的总和，然后从中减去数组中所有数的实际总和，差值即为缺失的数字，因为只缺失了一个数字，所以这种方法可以准确找到缺失的数字。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在计算从0到n的理论总和时选择使用高斯求和公式S = n * (n + 1) / 2而不是其他方法？
▷🦆
在实现中，实际总和是通过直接调用sum(nums)来计算的，这种方法在面对非常大的数组时是否存在性能问题？
▷🦆
如果数组nums中包含重复的数字，但仍然缺失一个数字，这种方法是否仍然有效？
▷