LeetCode 268 Missing Number —— 線性時間常數空間找出缺失數字

LeetCode 268 給定一個包含 0, 1, 2, ..., n 中 n 個互不相同數字的陣列，找出缺失的那一個。要求 O(n) 時間、O(1) 額外空間。

一、數學求和法（最直觀）

完整數列和 expected = n(n+1)/2，實際陣列和 actual，差值即為缺失數字。

int missingNumber(vector<int>& nums) {
    long long expected = 0, actual = 0;
    int n = nums.size();
    for (int i = 1; i <= n; ++i) expected += i; // 0~n 共 n+1 個數，但陣列長度為 n
    for (int v : nums) actual += v;
    return expected - actual;
}

注意：n 可達 10⁴~10⁵，int 足夠，但用 long long 更保險。

二、位運算異或法（更優雅，無溢位風險）

a ^ a = 0, a ^ 0 = a。將 0~n 與陣列所有元素異或，成對抵消，剩下的就是缺失值。

int missingNumber(vector<int>& nums) {
    int res = nums.size(); // 初始化為 n，因為索引只到 n-1
    for (int i = 0; i < nums.size(); ++i)
        res ^= i ^ nums[i];
    return res;
}

三、原地置換法（面試常考變體）

利用陣列下標與值的對應關係，將每個數字放到「應該在的位置」，最後掃描第一個 nums[i] != i 的位置。會修改輸入陣列，若不可修改則不適用。

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; ) {
        if (nums[i] < n && nums[i] != nums[nums[i]])
            swap(nums[i], nums[nums[i]]);
        else
            ++i;
    }
    for (int i = 0; i < n; ++i)
        if (nums[i] != i) return i;
    return n;
}

四、總結對比

五、測試用例

[0,1,3]        → 2
[0]            → 1
[1]            → 0
[0,1,2,3,4]    → 5
[]             → 0 (n=0 時陣列為空，缺失 0)