最小的k个数

2021年09月15日 阅读数:4
这篇文章主要向大家介绍最小的k个数,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

给定一个数组,找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。ios

  • 0 <= k <= input.length <= 10000
  • 0 <= input[i] <= 10000

方法一:直接排序

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int>ret;
        if(k==0||k>input.size()) return ret;
        sort(input.begin(),input.end());
        return vector<int>({input.begin(),input.begin()+k});
        }
};

sort函数用于C++中,对给定区间全部元素进行排序,默认为升序,也可进行降序排序。数组

sort(start,end,cmp)ide

1.sort函数没有第三个参数,实现的是从小到大(升序)排列函数

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int a[10]={9,6,3,8,5,2,7,4,1,0};
    sort(a,a+10);//指针
    for(int i=0;i<10;i++)
    cout<<a[i]<<endl;
    return 0;
}

2.须要在sort()函数里的第三个参数了,告诉程序我要从大到小排序spa

            须要加入一个比较函数compare(),此函数的实现过程以下指针

#include<iostream>
#include<algorithm>
using namespace std;
bool compare(int a,int b)
{   
return a>b;
}
int main()
{
int a[10]={9,6,3,8,5,2,7,4,1,0};
 sort(a,a+10,compare);//在这里就不须要对compare函数传入参数了   
for(int i=0;i<10;i++)
cout<<a[i]<<endl;
return 0;
}

 

方法二:堆排序

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        
        vector<int>res;
        if(k==0||k>input.size())
            return res;
        
        priority_queue<int, vector<int>> pq;
        for(int i=0;i<k;++i){
            pq.push(input[i]);
        }
        
        for(int i=k;i<input.size();++i){
            if(input[i]<pq.top()){
                pq.pop();
                pq.push(input[i]);
            }
        }
        
        while (!pq.empty()) {
            res.push_back(pq.top());
            pq.pop();
        }

        return res;
        
        }
};

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

上一篇: 基础篇
下一篇: 反转字符串