268-丢失的数字

LeetCode 268. Missing Number

LeetCode-268

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 1:

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.

method 1: 排序

排序后，如果元素和下标不对应，就是缺失的

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

时间复杂度：$O(nlogn)$

---

method 2: 求和

已经知道是[0,n]，累加之后再减去每个元素就知道哪个缺失了

等差数列求和：$S_n = \frac{(a_1 + a_n)n}{2}$

int missingNumber(vector<int>& nums) {
    int sum = nums.size() * (nums.size() + 1) / 2;
    for (auto n : nums) sum -= n;
    return sum;
}

时间复杂度：$O(n)$

---

method 3: 异或

下标和元素应该是一一对应的，所以全部异或之后，剩下的就是缺失的

int missingNumber(vector<int>& nums) {
    int res = nums.size();  // 补上下标的n
    for (int i = 0; i < nums.size(); i++) {
        res = res ^ i ^ nums[i];
    }
    return res;
}

时间复杂度：$O(n)$