优选算法_topk问题_快速排序算法_堆_C++
一.题目解析算法解析:快速排序算法找到所在区间再进行快速排序(递归)代码编写:class Solution { public: int findKthLargest(vectorint nums,int k) { srand(time(NULL)); return qsort(nums,0,nums.size()-1,k); } int qsort(vectorint nums,int l,int r,int k) { int leftl-1,rightr1; int keygetrandom(nums,l,r); int il; while(iright) { if(nums[i]key)swap(nums[left],nums[i]); else if(nums[i]key) i; else swap(nums[--right],nums[i]); } int cr-right1,bright-left-1; if(ck)return qsort(nums,right,r,k); else if(bck) return key; else return qsort(nums,l,left,k-b-c);//找第几大的元素 } int getrandom(vectorint nums,int l,int r) { return nums[rand()%(r-l1)l]; } };算法解析:堆topk问题用数据结构堆很好解决,第几大元素,我们只需要建立一个小根堆(priority_queue(int,vectorint,greaterint)),循环-1.依次推进,判断堆的大小是否超过k(遍历完成后堆顶就是topk元素)代码编写:class Solution { public: int findKthLargest(vectorint nums, int k) { priority_queueint,vectorint,greaterintheap; for(auto x:nums) { heap.push(x); if(heap.size()k)heap.pop(); } return heap.top(); } };
)
