题意

输入n个数，按升序输出其中最小的k个数

限制，$n\le 1000n\backslash leq\; 1000$,$1\le val\le 100001\backslash leq\; val\; \backslash leq\; 10000$

方法

内置排序与读入读出

我们直接实现题意，读入n个数，对他们调用C++内置排序，输出前k个即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)
int a[1010];
int main(){
    int n,k;
    while(cin>>n>>k){
        rep(i,0,n){ // 读入
            scanf("%d",a+i);
        }
        sort(a,a+n); // 排序
        rep(i,0,k){ // 输出
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 读入数据为$O(n)O(n)$,排序代价$O(n\cdot log(n))O(n\; \backslash cdot\; log(n))$,输出代价$O(k)O(k)$,总时间复杂度$O(max(n\cdot log(n),k))O(max(n\backslash cdot\; log(n),k))$

空间复杂度: 主要是数组存放，$O(n)O(n)$

基于计数的实现

注意到这里的整数范围还算小，所以也可以考虑基于计数来做

以样例数据为例, 数值是 1,3,5,7,2,我们的计数数组为

有了基于计数的统计表以后，我们再通过游标找k次最小值，输出即可

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)
int main(){
    int n,k;
    while(cin>>n>>k){
        vector<int> cnt(10010,0);
        rep(i,0,n){
            int v;
            scanf("%d",&v);
            cnt[v]++; // 计数
        }
        int itr = 1;
        rep(i,0,k){
            while(!cnt[itr])itr++; // 找到下一个最小的
            cnt[itr]--;
            printf("%d ",itr); // 输出
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 读入数据为$O(n)O(n)$,输出代价$O(max(k,max(val)))O(max(k,max(val)))$,总时间复杂度$O(max(n,k,max(val)))O(max(n,k,max(val)))$

空间复杂度: 我们记录的大小不再和数组长度相关，而是和数据大小相关,所以空间复杂度为$O(max(val)-min(val))O(max(val)-min(val))$