题目分析

这个题目我做过许多次了，之前是使用Python语言写的代码，这次用C++来实现一下，题目难度不大，小伙伴们能够想到多少种方法呢？

暴力法

直接遍历查找，每一个数都从数组中进行查找，看一下是否存在。

算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(1)$**。

提交时会TLE，因此不能使用这个方法。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        for (int i = 0; i <= nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i == nums[j]) break;
                if (j == nums.size() - 1) return i;
            }
        }
        return -1;
    }
};

数组

使用空间来换取时间，来一个数则该索引值+1，最后遍历数组，看一下哪一个索引对应的值为0即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        vector<int> arr(nums.size() + 1, 0);
        for (int x : nums) arr[x] += 1;
        for (int i = 0; i < arr.size(); i++) if (arr[i] == 0) return i;
        return -1;
    }
};

哈希表

使用哈希表同样的道理，可以先将0~n的所有元素都加入哈希表中，然后从nums中逐一删除，最后剩余元素就是缺失的元素。

也可以从nums中逐一添加进哈希表，然后查找0~n的所有元素，如果找不到说明该元素是缺失元素，

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>
#include<unordered_set>

using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> hashSet;
        for (int i = 0; i <= nums.size(); i++) hashSet.insert(i);
        for (int x : nums) hashSet.erase(x);
        return *hashSet.begin();
    }
};

优化数组

都是正数的题目可以在原数组上进行修改，不需要另外开辟数组。

如果某个数等于k，那么我们让k对应的索引变成相反数。那么最后是正数的位置说明没有相应的k让其变化。

但是这个方法需要考虑很多的情况，代码量较长。

最大值问题，数组长度为n，最大值为n，因此不能改变nums[n]对应的值，会数组越界。因此我们要对最大值进行特判。
0的问题，如果某个位置的值是0，如nums[k] = 0,那么我们修改k的时候还是0，最后查询时会出错。因此我们先判断0是否存在，如果不存在直接返回0。如果存在，我们对修改后的数组查询时，如果存在正数，则返回对应索引，如果不存在，说明恰好修改的是0，因此返回0的索引。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(1)$**。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        pair<vector<int>::iterator, vector<int>::iterator> minMax = minmax_element(nums.begin(), nums.end());
        int mini = *minMax.first, maxi = *minMax.second;
        if (maxi < nums.size()) return nums.size();
        if (mini != 0) return 0;
        for (int i = 0; i < nums.size(); i++) if (abs(nums[i]) < maxi) nums[abs(nums[i])] *= -1;
        for (int i = 0; i < nums.size(); i++) if (nums[i] > 0) return i;
        for (int i = 0; i < nums.size(); i++) if (nums[i] == 0) return i;
        return -1;
    }
};

数学

在优化数组中，我们遍历了数组4次，如何更快更高效呢？

数组中的数组是从0~n的，因此和是已知的，我们计算之和，然后再减数组中的每一个元素，即可求出缺失元素。

在Python中不会超出数据的表示范围，但是C++中要小心，因此利用等差数列求和公式是不安全的，这里给出一种更好的处理方法。

我们要计算0~n这n个数的和，然后减去nums数组中的和，可以减去数组中的元素，如果结果小于等于0，那么就加上一个数k，直到结果变为正数为止，其中k从0到n。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(1)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int k = 0, res = 0;
        for (int x : nums) {
            res -= x;
            while (res <= 0 && k <= nums.size()) res += k++;
        }
        return res;
    }
};

位运算

本题除了数学方法以外，也有其他巧妙的方法——位运算。

位运算是满足交换律的，而且满足如下两个式子。
$x ^ x = 0 \ \ x ^ 0 = x$

因此我们先从0异或到n，再异或数组中的所有元素，那么除了缺失的元素以外，其他的元素都异或了两次，都变成了0，0异或缺失的元素，最后得到的结果就是缺失的元素。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(1)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 1; i <= nums.size(); i++) res ^= i;
        for (int x : nums) res ^= x;
        return res;
    }
};

刷题总结

题目虽然简单，但是考察了许多重要的知识点，如数据的表示范围，位运算等等，希望小伙伴们能够掌握后面三种方法。