题解 | #输入n个整数，输出其中最小的k个#

HJ58 输入n个整数，输出其中最小的k个

题目描述

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

方法一：暴力方法

解题思路

针对方法一，我们直接将所给的数据进行排序，然后输出其中最小的k个即可。

解题代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    while(cin>>n>>k)
    {   //输入n和k
        vector<int> num;
        for(int i=0;i<n;i++)
        {   //逐个储存n个整数
            int temp;
            cin>>temp;
            num.push_back(temp);
        }
        sort(num.begin(),num.end());//对n个数进行升序排序
        for(int i=0;i<k-1;i++)
        {   //输出前k个数字
            cout<<num[i]<<' ';
        }
        cout<<num[k-1]<<endl;//最后一个数字输出后不要输出空格了
    }
    return 0;
}

复杂度分析

时间复杂度：使用快排，时间复杂度为$O(NlogN)O(NlogN)$。

空间复杂度：没有引入新的额外内存地址空间，因此空间复杂度为$O(1)O(1)$

方法二：堆方法

解题思路

对于方法二，我们采用了堆排序，首先读入数据，然后创建一个大小为k的堆，并且对于后续数据则选择小于堆里面的数据进行加入，并最后对大小为k的堆进行排序，得到最后答案。

解题代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 0, k = 0;
    while(cin >> n >> k)
    {
        vector<int> vec;
        int num = 0;
        while(n--)
        {
            cin >> num;
            vec.push_back(num);
        }
        //建堆k*logk
        vector<int> heap(vec.begin(), vec.begin() + k);
        make_heap(heap.begin(), heap.end(), less<int>());
        //插入(n - k)*logk
        for(int i = k; i < vec.size(); i++)
        {
            if(vec[i] < heap[0])
            {
                //插入一个更小的
                heap.push_back(vec[i]);
                push_heap(heap.begin(), heap.end());
                //弹出一个最大的
                pop_heap(heap.begin(), heap.end());
                heap.pop_back();
            }
        }
        //从小到大输出,k*logk + k
        sort(heap.begin(), heap.end());
        for(int i = 0; i < heap.size(); i++)
        {
            cout << heap[i];
            if(i != heap.size() - 1)
            {
                cout << " ";
            }
        }
        cout << endl;
    }
}

复杂度分析

时间复杂度：大小为k的堆，调整的过程是对数复杂度，时间复杂度为$O(nlogk)O(nlogk)$

空间复杂度：使用了大小为k的堆，因此空间复杂度为$O(k)O(k)$