偶遇计算机考研408真题--找出数组中未出现的最小整数

阳光穿透心脏的1/2处 2022-12-09 15:50 74阅读 0赞

## 题目描述： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70_pic_center]

## 心得： ##

本人刚升上大二，数据结构才刚开始学，并没有想到啥算法，尽管做过几道类似leetcode或者牛客网的题目，但是一直没想到。当时我一直困在把负数置0，比较前后关系这里，并没有跳出来，想到别的办法。后来看了一下答案，感觉廓然开朗！

## 思路分析： ##

我们可以考虑开一个数组B，用来统计，对于原来数组的为0的，小于0的，或者A\[i\]大于n的通通忽略，因为最小整数的范围是【1，n+1】，我们只需要将符合的数在B数组钟置于1，即B\[a\[i\]-1\]=1,然后对B数组进行遍历，找到第一个为0的元素的下标+1即返回最小整数，否则返回n+1

### 代码实现： ###

int find_the_diasppar_min_number(int arr[],int length){
        
        int i=0,*B;
        B=(int *)malloc(sizeof(int)*length);//分配空间
        memset(B,0,sizeof(int)*length);初始值设为0
    
        for(i=0;i<length;i++)
            if(arr[i]>0&&arr[i]<=length)
                B[arr[i]-1]=1;
            for(i=0;i<length;i++)
                if(B[i]==0) break;
            return i+1;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/6746d53832e8445098ceec43e6822b29.png