408 2018年大题 找出一个未出现最小正整数

题目描述

输入样例

[-5,1000,3,3,1]

输出样例

2

---

算法 时间复杂度： O ( n ) O(n) O(n) (遍历了整个数组) 空间复杂度： O ( n ) O(n) O(n) (使用了一个b数组)

用一个数组b来判断在数组中数值为[1,n]的数是否出现过。
这个数组b就类似于图论中的st数组用来判断一个点是否被遍历过。

C++ 代码

#include
using namespace std;
const int MaxSize = 100; 

int findMinNum(int q[],int len)
{
    int idx=-1,*b;
    b=(int*)malloc(sizeof(int)*n);  //设计一个b的指针数组，用于判断[1,n]之间的数是否在数组中出现过
    memset(b,0,sizeof *b);  //b的大小就是n，每个值初始设为0
    
    for(int i=0;i=0 && q[i]<=len)
        {
            b[q[i]-1]=1;
        }
    }
    for(int i=0;i