题解 | #缺失数字#

缺失数字

http://www.nowcoder.com/practice/9ce534c8132b4e189fd3130519420cde

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]>ii.

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), 没有额外空间。
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-10 14:00
林子大了什么鸟都有啊,我觉得我说的已经很客气了,阴阳谁呢
牛客62656195...:应该不是阴阳吧?你第一次注册的时候boss就说你是牛人
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 12:10
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 11:31
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务