nc101 缺失数字

1. 根据等差数列的求和公式

因为数组为0-n， 且缺一个数， 所以用前n个数的和n*(n-1)/2减数组各项之和就可以了。

这里我用了STL里面的accumulate, 用法也比较简单，头两个形参指定要累加的元素范围，第三个形参则是累加的初值。

如果自己使用的话，注意加上头文件#include <numeric>.

class Solution {
public:
    int solve(vector<int>& a) {
        int n = a.size();

        return n*(n+1)/2 - accumulate(a.begin(), a.end(), 0);
    }
};
  • 时间复杂度： O(n), 因为accumulate要遍历数组中n个数。
  • 空间复杂度：O(1)， 没有额外空间。

2. 二分答案

观察到该数组有如下性质：

  • 在遇到缺的数之前，有a[i] == i
  • 遇到缺的数之后，有a[i] > i

如图所示,以缺3为例：
图片说明

012三项满足a[i]==i, 345三项满足a[i]-1==i

所以此问题具有很明显的单调性质，故可以二分答案， 套用二分模板就可以。目标是第一个a[i]>i的i.

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 找缺失数字
     * @param a int整型vector 给定的数字串
     * @return int整型
     */
    int solve(vector<int>& a) {
        // write code here
        int n = a.size();
        int l = 0, r = n; // 特别注意，上界有可能在数组外面，切记！！！

        while (l < r) {
            int mid = (l+r) >> 1;
            // 如果 a[i]==i 说明mid及mid以左的数都不是目标值
            if (a[mid] == mid) l = mid+1;
            // 否则mid在左侧， 可能是mid
            else r = mid;
        }
        // 最后出来的时候，l即为所求
        return l;
    }
};
  • 时间复杂度： O(logn), 标准的二分查找
  • 空间复杂度： O(1)， 没有额外空间。