268. Missing Number.md

268. Missing Number

思路

思路一

先将数组进行排序，然后从前往后遍历，若某元素与其下标不等，说明缺失了下标这个数。
时间复杂度O(nlogn)

思路二

因为没有缺失的数组的和是很容易知道的，用这个和减去实际和就是缺失值。
想知道没有缺失的数组的和，先应该找出数组的最大值max_num，若最大值为size-1，则缺失的就是size这个值，直接返回即可。
否则缺失值就为 result = (max_num + 1)*max_num/2 - sum 。
注意上式子第一项很容易存在溢出，所以将上式子拆成 2*result = ∑(max_num + 1 - 2 * nums[i]), 这样就不容易溢出了。
时间复杂度O(n), 空间复杂度O(1)

思路三

使用一个例子来看一下算法的运算过程：
nums: 0 1 2 4 5 6 7 (缺失3)
index: 0 1 2 3 4 5 6
可见如果再加上一个nums.size()和缺失值的话，所有的数字都是成对的，对这些数字进行异或操作会最终会得0。
所以如果不加缺失值，异或得到的结果就是缺失值。
此算法就肯定不会溢出了, 时间复杂度O(n), 空间复杂度O(1)

C++

思路二

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int max_num = -1;
        for(int num: nums) 
            if(max_num < num) max_num = num;
    
        if(max_num == nums.size() - 1) 
            return nums.size();
        
        int result_2 = 0;
        for(int num: nums)
            result_2 += (max_num + 1 - 2 * num);
        
        return result_2 / 2;
    }
};

思路三

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