leetcode 268. Missing Numbers (XOR!!)

给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数.

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3,（n为数组中元素个数）因为有 3 个数字,所以所有的数字都在范围 [0,3] 内.2 是丢失的数字,因为它没有出现在 nums 中.

示例 2：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内.8 是丢失的数字,因为它没有出现在 nums 中.

提示：

n == nums.length
1 <= n <= 10⁴
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

思路一：异或

首先将从0到nAll values ​​of are XORed once,This is to record all the values,Then XOR each value in the array,Because the same number is XORed2times have no effect on the original value,即 a ^ b ^ b =a .

Then in the end, only the number that did not appear is left.

class Solution {
    
public:
    int missingNumber(vector<int>& nums) {
    
        int ans=0;
        int n=nums.size();
        for(int i=0;i<=n;++i)
            ans^=i;
        for(vector<int>::iterator it=nums.begin();it!=nums.end();++it)
            ans^=(*it);
        return ans;
    }
};

思路二： 作差

先从0一直加到n,Record the sum when all numbers are present sum,Then add each value in the array he,他们的差值（sum-he）That is, the number that does not appear.

class Solution {
    
public:
    int missingNumber(vector<int>& nums) {
    
        int sum=0,he=0;
        sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<=n;++i)
            sum+=i;
        for(vector<int>::iterator it=nums.begin();it!=nums.end();++it)
            he+=(*it);
        return sum-he;
    }
};

思路三：排序

对数组进行排序,If the serial number and value of the corresponding position are not equal,Then the ordinal is the missing number.

class Solution {
    
public:
    int missingNumber(vector<int>& nums) {
    
        sort(nums.begin(),nums.end());
        int n=nums.size(),i=0;
        for( ;i<n;++i){
    
            if(i!=nums[i])
                break;
        }
        return i;  //If the last number is missing,Then the loop end conditioni==n,最后返回的也是n
    }
};