題目網址：https://leetcode.cn/problems/missing-number/

題意：原本有一包含 [0, n] 總共 n + 1 個數的 array, 今給一只有 n 個數的 array nums, 找出缺失的數。

Solution 1：

想法：先將 nums 排序, 然後用 loop 檢查第 i 個數是否在 nums 中

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != i) {
                return i;
            }
        }

        return nums.size(); // Example 2
    }
};
  • time：$O(n \cdot log(n))$ ➔ sorting
  • space：$O(1)$ ➔ sorting 後 data 仍儲存在 nums 中, 不需要額外空間

Solution 2：

想法：先計算 [0, n] 這 n + 1 個數之和, 然後扣掉 nums 中 data 之和, 即可得到缺失的數

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        const int sum = accumulate(nums.begin(), nums.end(), 0); // 取得 nums 總和
        const int total = nums.size() * (nums.size() + 1) / 2; // 計算 0 ~ n 之和
        return total - sum; // 相減即為缺值
    }
};
  • time：$O(n)$ ➔ 遍例 nums 計算所有 data 之和
  • space：$O(1)$ ➔ 只需常數空間

Solution 3：

想法：利用 XOR 中 a ^ a = 0 且 0 ^ a = a 的特性（還有交換性）

e.g. [0, 1, 2, 3] ^ [0, 1, 3] = 2

XOR：

  • 0 ^ 0 = 0
  • b ^ b = b
  • 0 ^ a = a
  • a ^ b ^ b = a ^ (b ^ b) = a ^ 0 = a
  • 交換性：b ^ a ^ b = a ^ (b ^ b) = a ^ 0 = a
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 1; i <= nums.size(); ++i) {
            res = res ^ i ^ nums[i - 1];
        }
        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(1)$ ➔ 只需常數空間