13-丢失的数字

自己的做法

算法思想

因为数组的长度是 n，而数字的范围是[0, n]。所以只差一个数字。

想到使用数列来做。具体操作是：

• 获得数组长度n，并根据长度算出 0 ~ n 项等差数列的和。
• 遍历数组，求出数组每项总和
• 使用两项相减，即为缺失的数字

算法实现

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int size = nums.size();
        int ideal_sum = (size + 1) * size / 2;
        int sum = 0;
        for(int i = 0; i < size; i++) {
            sum = sum + nums[i];
        }
        return ideal_sum - sum;
    }
};

性能分析

时间复杂度：遍历数组，为$O(n)$。

空间复杂度：使用三个变量，为$O(1)$。

其他解法

该题还可以使用哈希表和排序来做，不过排序时间复杂度为$O(n * logn)$，哈希表空间复杂度为$O(n)$。

都不是最优解。

官方解法

算法思想

使用异或运算(即相同为0，不同为1)。首先要知道：

1. 0 和 任何数进行异或运算的结果仍为该数，即0 ^ a = a。
2. 一个数和它自己进行异或结果为0 ，即a ^ a = 0。
3. 异或运算满足结合律。

根据这两条，可以解出该题。

因为数组有n个数，范围为[0,n]，所以除了缺失的数组，剩下的数字在数组中和取值范围中都有一个。

因此将[0, n]个数字和数组中每个元素进行异或运算，由于满足结合律且除了缺失数字其他都是两两一对，最后会变成：

0 ^ 缺失的数字 ，结果就是缺失的数字，即为答案。

可以使用数组索引和该索引对应数字依次进行异或运算，但这样只是[0, n - 1]和数组每个数字进行了异或运算，因此可以将结果变量初始值设为n，然后进行异或操作即可。

算法实现

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

性能分析

时间复杂度：遍历一个数组，$O(n)$。

空间复杂度：只使用了一个变量，$O(1)$。