leetcode 268. 丢失的数字（异或！！）

给定一个包含 [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到n的所有值都异或一遍，这样算是将所有的值都记录一遍，再对数组中的每一个值异或，因为同一个数异或2次对原值没有影响，即 a ^ b ^ b =a 。

那么到最后就只剩下没有出现的那个数字了。

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

思路二： 作差

先从0一直加到n，记录所有数都出现时的总和 sum，再将数组中的每个值都相加 he，他们的差值（sum-he）即为没有出现的数字。

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

思路三：排序

对数组进行排序，如果对应位置的序号和数值不相等，那么序号就是缺失的数字。

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;  //如果是最后一个数缺失，那么循环结束条件时i==n，最后返回的也是n
    }
};
1
2
3
4
5
6
7
8
9
10
11
12