首页 > 代码库 > 剑指offer--最小的K个数
剑指offer--最小的K个数
剑指offer--最小的K个数
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
以前以为排序掌握一个快排就ok了， 其他的算法是鸡肋，但是这题给我的感觉是： 其他的排序也是非常有用的，不同的算法在不同的应用场景下有着不同的效果。
答案来自 牛客网 https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&tqId=11182&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
class Solution {
public:
void heapSort(vector<int> &input, int start, int end){
for(int i = end-1; i > start; --i ) {
int j = (i + start - 1)/2;
if(input[j] > input[i]){
int tmp = input[i];
input[i] = input[j];
input[j] = tmp;
}
}
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> ans;
if(k > input.size()){
return ans;
}
for(int i=0; i<k; ++i){
heapSort(input, i, input.size());
ans.push_back(input[i]);
}
return ans;
}
};
剑指offer--最小的K个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。