牛客题霸 [ 缺失数字] C++题解/答案

题目描述

从0,1,2,…,n这n+1个数中选择n个数,找出这n个数中缺失的那个数,要求O(n)尽可能小。

题解:

我们可以用map来标记已出现过的数字
因为数组长度给出是len,因为是连续的数字,且有0,所以查找时循环0~len+1,然后看每个i是否出现过,没出现过的就是我们要找的答案

代码:

class Solution {
   
public:
    /** * 找缺失数字 * @param a int整型一维数组 给定的数字串 * @param aLen int a数组长度 * @return int整型 */
    int solve(int* a, int aLen) {
   
        // write code here
        map<int,int>mp;
        for(int i=0;i<aLen;i++)
        {
   
            mp[a[i]]=1;
        }
        for(int i=0;i<=aLen;i++)
        {
   
            if(mp[i]==0)return i;
        }
    }
};