TOP k问题
(1) 最小堆方法
#include
using namespace std;
void heap_adjust(vector&nums,int i, int len) {
//建立小顶堆,以i节点为根，堆大小为len+1
intminid = i;
intleft = i * 2 + 1;
intright = left + 1;
if(left <= len && nums[left] < nums[minid]) minid = left;
if(right <= len && nums[right] < nums[minid]) minid = right;
if(minid != i) {
swap(nums[i],nums[minid]);//找到最小值，进行交换
heap_adjust(nums,minid, len);//递归调整以minid为根的堆
}
}
vectortopk(vector&nums, int k) {
//建一个大小为k的堆
for(int i = k - 1; i >= 0; i--) {
heap_adjust(nums,i, k - 1);
}
for(int j = nums.size() - 1; j >= k; j--) {
if(nums[j] > nums[0]) {//如果nums[j]比堆顶元素nums[0]小，则不需要改变原来的堆
//如果nums[j]比堆顶元素nums[0]大，那么用nums[j]替换堆顶元素nums[0]，在替换之后，需要调整堆来维持最小堆的性质
swap(nums[0],nums[j]);
heap_adjust(nums,0, k - 1);
}
}
vectorres(nums.begin(),nums.begin() + k);
returnres;
}
(2)快排
int partition(vector&nums,int left, int right) {
intpivot = left + rand() % (right - left + 1);
swap(nums[pivot],nums[left]);
inttmp = nums[left];
while(left < right) {
while(left < right && nums[right] < tmp) {
right--;
}
nums[left]= nums[right];//从后往前第一个大于tmp的值
while(left= tmp) {
left++;
}
nums[right]= nums[left];//从前往后第一个小于tmp的值
}
nums[left]= tmp;//left前的都大于nums[left]，left后的都小于nums[left]
returnleft;
}
vectorquicksort(vector&nums,int left, int right, int k) {
intpos = partition(nums, left, right);
if(pos == k) {
vectorres(nums.begin(),nums.begin() + k + 1);
returnres;
}
elseif (pos < k) {
returnquicksort(nums, pos + 1, right, k);
}
else{
returnquicksort(nums, left, pos - 1, k);
}
}
int main() {
vectornums{15,6,7,8,8,10,16,12,13,14 };
intk = 4;
vectorres= quicksort(nums, 0, nums.size() - 1, k - 1);
system("pause");
return0;
}
