题解：P1138 第 k 小整数

· · 题解

正如题解区的大佬们所说，此题方法很多。

第一种：计数排序。

可明显，题目给我们的正整数不会很大，于是我们就可以用。

循环输入，对应的地方如果为 1 时，即有相同的数，不增加记录数字个数的变量；否则标记为 1 后那个变量加一。

每次取最大值，可以为后面减少部分数据的循环。

循环结束后，如果变量小于 m 时，即无解。

循环从 1 到最大值即可，令一个变量初始为 1 后，每次循环如果当前有元素就加一，如果该变量为 m 时输出 i 即可。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,t,ma;
unordered_map<int,bool> mp;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(mp[x]==0){
            t++;
        }
        mp[x]=1;
        ma=max(ma,x);
    }
    if(t<m){
        cout<<"NO RESULT";
    }
    t=0;
    for(int i=1;i<=ma;i++){
        if(mp[i]){
            t++;
        }
        if(t==m){
            cout<<i;
            return 0;
        }
    }
    return 0;
}

第二种，去重：

很好理解，此题由题目可知要去重，一样简单，代码就不放了。

后记：谢谢管理员审核，管理员辛苦了。