題目描述 [最小的k個(gè)數(shù)]
輸入n個(gè)整數(shù)芜茵，找出其中最小的K個(gè)數(shù)杂穷。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字饰抒，則最小的4個(gè)數(shù)字是1,2,3,4,阔加。
解題思路
維護(hù)一個(gè)最小堆
代碼
class Solution {
public:
void maxHeap(vector<int> &nums, int i, int high){
int left = 2*i+1, right = 2*i+2;
int largest;
if(left<high&&nums[left]<nums[i]) largest = left;
else largest = i;
if(right<high&&nums[right]<nums[largest]) largest = right;
if(largest!=i){
swap(nums[i], nums[largest]);
maxHeap(nums, largest, high);
}
}
void bulidHeap(vector<int> &nums){
for(int i=nums.size()/2-1; i>=0; i--){
maxHeap(nums, i, nums.size());
}
}
void heapSort(vector<int> &nums){
bulidHeap(nums);
for(int i=nums.size()-1; i>0; i--){
swap(nums[0], nums[i]);
maxHeap(nums, 0, i);
}
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
int n=input.size();
vector<int> res;
if(input.size() < k || k <= 0) return res;
vector<int> nums(input.begin(), input.begin()+k);
heapSort(nums);
for(int i=k;i<n;i++){
if(input[i]<nums[0]){
nums[0] = input[i];
heapSort(nums);
}
}
sort(nums.begin(), nums.end());
return nums;
}
};
二刷
嗯奢啥，自己寫堆太累秸仙，筆試面試一時(shí)半會(huì)也寫不好
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
if(input.size()<k || input.size()==0 || k==0) return res;
for(int i=0;i<input.size();i++){
if(res.size()<k) res.push_back(input[i]);
else{
make_heap(res.begin(), res.end());
if(input[i]<res.front()){
pop_heap(res.begin(), res.end());
res.pop_back();
res.push_back(input[i]);
push_heap(res.begin(), res.end());
}
}
}
return res;
}
};
