LeetCode: 268 Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

问题

给定一个包含 n 个不同数字的数组 nums，这些数字在范围 [0, n] 内，返回该范围内唯一缺失的数字。

解决方案 1

求和公式法

Approach 1 / 方法 1

This solution uses the sum formula for the first n natural numbers. The sum of numbers from 0 to n is given by the formula n * (n + 1) / 2. By calculating the sum of the numbers in the array and subtracting it from this expected sum, we get the missing number.

该解决方案使用前 n 个自然数的求和公式。0 到 n 的数字之和由公式 n * (n + 1) / 2 给出。通过计算数组中数字的和并从这个预期和中减去它，我们得到缺失的数字。

Implementation / 实现

python

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

Explanation / 解释

1. Calculate the Length of nums / 计算 nums 的长度

   n = len(nums)

   • English: We calculate n, which is the length of the array nums.
   • Chinese: 我们计算 n，即数组 nums 的长度。

2. Calculate the Expected Sum / 计算预期和

   expected_sum = n * (n + 1) // 2

   • English: We calculate the expected sum of numbers from 0 to n using the formula n * (n + 1) / 2.
   • Chinese: 我们使用公式 n * (n + 1) / 2 计算 0 到 n 的数字的预期和。

3. Calculate the Actual Sum of nums / 计算 nums 的实际和

   actual_sum = sum(nums)

   • English: We calculate the actual sum of the numbers in the array nums.
   • Chinese: 我们计算数组 nums 中数字的实际和。

4. Return the Difference Between Expected and Actual Sum / 返回预期和与实际和的差值

   return expected_sum - actual_sum

   • English: The missing number is the difference between the expected sum and the actual sum.
   • Chinese: 缺失的数字是预期和与实际和之间的差值。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the length of the array nums. We calculate the sum of the elements in nums, which takes O(n) time.
• Space Complexity / 空间复杂度: O(1), as we use only a constant amount of extra space.

Key Concept / 关键概念

• Sum Formula / 求和公式: This approach leverages the formula for the sum of the first n natural numbers to identify the missing number by comparing the expected and actual sums.
• 求和公式: 该方法利用前 n 个自然数的求和公式，通过比较预期和与实际和来识别缺失的数字。

解决方案 2

位操作法

Approach 2 / 方法 2

This solution uses XOR (exclusive OR) bitwise operations. The idea is that XORing a number with itself results in 0, and XORing any number with 0 results in the number itself. By XORing all the numbers from 0 to n and all the numbers in the array, the missing number will be the only number left.

该解决方案使用异或（XOR）位操作。其思想是，数字与自身进行异或运算结果为 0，而任何数字与 0 进行异或运算结果为该数字本身。通过对从 0 到 n 的所有数字和数组中的所有数字进行异或运算，缺失的数字将是唯一剩下的数字。

Implementation / 实现

python

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = len(nums)
        for i, num in enumerate(nums):
            missing ^= i ^ num
        return missing

Explanation / 解释

1. Initialize the Missing Number with n / 使用 n 初始化缺失的数字

   missing = len(nums)

   • English: We initialize missing with n, which is the length of the array nums.
   • Chinese: 我们使用 n，即数组 nums 的长度，初始化 missing。

2. Iterate Over All Numbers and Indices in nums / 遍历 nums 中的所有数字和索引

   for i, num in enumerate(nums):

   • English: We loop through each index i and corresponding number num in the array nums.
   • Chinese: 我们遍历数组 nums 中的每个索引 i 和相应的数字 num。

3. XOR missing with i and num / 对 missing 与 i 和 num 进行异或操作

   missing ^= i ^ num

   • English: We XOR the current value of missing with the index i and the number num. This effectively cancels out the numbers that are present in both the array and the range [0, n], leaving the missing number.
   • Chinese: 我们将 missing 的当前值与索引 i 和数字 num 进行异或操作。这有效地抵消了数组和范围 [0, n] 中同时存在的数字，留下缺失的数字。

4. Return the Missing Number / 返回缺失的数字

   return missing

   • English: The final value of missing is the missing number in the array.
   • Chinese: missing 的最终值是数组中缺失的数字。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the length of the array nums. We iterate through each element of nums, which takes O(n) time.
• Space Complexity / 空间复杂度: O(1), as we use only a constant amount of extra space.

Key Concept / 关键概念

• Bitwise XOR Operation / 位操作 XOR: This approach efficiently finds the missing number by leveraging the properties of XOR, which cancels out numbers that appear twice.
• 位操作 XOR: 该方法通过利用 XOR 的特性（重复出现的数字被抵消）高效地找到缺失的数字。

Comparison / 比较

1. Efficiency / 效率:

   • Sum Formula Approach / 求和公式法: Simple and intuitive but involves potentially large sums.
   • Bitwise XOR Approach / 位操作 XOR: Slightly more complex but avoids dealing with large sums and uses bitwise operations.

2. Use Case / 使用场景:

   • Sum Formula / 求和公式: Preferred when working with smaller arrays or when simplicity is important.
   • Bitwise XOR / 位操作 XOR: Preferred when working with larger arrays or when looking for a solution that avoids potential integer overflow issues.

Summary / 总结

• English: Both the sum formula and bitwise XOR approaches are effective

  for finding the missing number. The sum formula is straightforward, while the XOR method is more optimized and avoids handling large sums.

• Chinese: 求和公式法和位操作 XOR 方法都能有效地找到缺失的数字。求和公式法直观简单，而 XOR 方法更优化，避免了处理大数问题。

Tips / 提示

• English: Use the XOR approach if you want an efficient and optimized solution, especially for larger arrays.
• Chinese: 如果想要一个高效和优化的解决方案，尤其是对于较大的数组，使用 XOR 方法。

Solution Template for Similar Questions / 提示

• English: Consider both the sum formula and bitwise XOR approaches depending on the specific requirements of bit manipulation or mathematical problems.
• Chinese: 根据位操作或数学问题的具体要求，考虑求和公式和位操作 XOR 方法。

5 More Similar Questions / 推荐5问题

1. LeetCode 136. Single Number
2. LeetCode 287. Find the Duplicate Number
3. LeetCode 389. Find the Difference
4. LeetCode 41. First Missing Positive
5. LeetCode 448. Find All Numbers Disappeared in an Array

Recommended Resources / 推荐资源

• English: Practice both the sum formula and XOR methods to solidify your understanding of these different approaches to finding missing numbers.
• Chinese: 练习求和公式和 XOR 方法，以巩固对这些寻找缺失数字的不同方法的理解。

Missing Number – Blind 75 – Leetcode 268 – Python by NeetCode