268.Missing Number

Tags: Math Array Bit Manipulation

Links: https://leetcode.com/problems/missing-number/

---

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

---

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sum = (1 + n) * n / 2;
        return sum - accumulate(nums.begin(), nums.end(), 0);
    }
};

用等差数列的求和公式求出0到n之间所有的数字之和，然后再遍历数组算出给定数字的累积和，然后做减法，差值就是丢失的那个数字

位运算方法：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (int i = 0; i < n; ++i) sum ^= nums[i] ^ i;

        return sum ^ n;
    }
};

既然0到n之间少了一个数，我们将这个少了一个数的数组合0到n之间完整的数组异或一下，那么相同的数字都变为0了，剩下的就是少了的那个数字了

二分的方法，虽然多余，但是如果一开始给出的数组是有序的，那么二分显然是最优的。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n;

        sort(nums.begin(), nums.end());
        while (left < right) {
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > middle) right = middle;
            else left = middle + 1;
        }

        return left;
    }
};