Easy

题目描述

给定一个包含 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 中。

提示：

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • nums 中的所有数字都是唯一的

进阶： 你能否实现线性时间复杂度、仅使用额外常数空间的算法？

解题思路

解题思路

这道题有多种解法，我们来分析几种常见的方法：

方法一：数学求和（推荐）

关键观察：范围 [0, n] 内所有数字的和是固定的，可以用等差数列求和公式计算：sum = n * (n + 1) / 2。而数组中所有元素的和可以直接遍历得到。两者相减就是缺失的数字。

方法二：异或运算

异或运算有一个重要性质：a ^ a = 0 和 a ^ 0 = a。我们可以将范围 [0, n] 内的所有数字与数组中的所有数字进行异或，相同的数字会抵消，最终剩下的就是缺失的数字。

方法三：排序 + 二分查找

先排序，然后二分查找第一个 nums[i] != i 的位置，该位置就是缺失的数字。

方法四：哈希表

用哈希表记录所有出现的数字，然后遍历 [0, n] 找到不在哈希表中的数字。

从时间和空间复杂度考虑，数学求和方法最优，只需要 O(n) 时间和 O(1) 空间。

代码实现

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }
};

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

public class Solution {
    public int MissingNumber(int[] nums) {
        int n = nums.Length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        foreach (int num in nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }
}

var missingNumber = function(nums) {
    const n = nums.length;
    const expectedSum = n * (n + 1) / 2;
    const actualSum = nums.reduce((sum, num) => sum + num, 0);
    return expectedSum - actualSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数学求和法异或运算法排序+二分法哈希表法
时间复杂度O(n)O(n)O(n log n)O(n)
空间复杂度O(1)O(1)O(1)O(n)

相关题目