LeetCode 268 Missing Number：缺失數字

題目描述

給定包含 0, 1, ..., n 中 n 個數的陣列，找出缺失的那一個數。

解法一：等差數列求和

期望總和 (n+1)*n/2 減去陣列實際和，差值即為缺失數。時間 O(n)，空間 O(1)。

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

解法二：排序後掃描

排序後逐一比對索引與值，首個不等處即為缺失數。時間 O(n log n)，空間 O(1)（或 O(log n) 排序棧）。

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();
    }
};

總結

數學求和法最優；若允許修改陣列，亦可用原地置換（Cyclic Sort）達到 O(n) 時間、O(1) 空間。