堆排序

建堆后，弹出k-1个数，堆顶的就是第k大的数。

  1. class Solution {
  2. public:
  3.     void maxHeapDown(vector<int>& nums,int father,int heapSize){
  4.         int l = father*2+1;
  5.         int r = father*2+2;
  6.         int largest = father;
  7.         if(l<heapSize&&nums[l]>nums[largest]){
  8.             largest = l;
  9.         }
  10.         if(r<heapSize&&nums[r]>nums[largest]){
  11.             largest = r;
  12.         }
  13.         if(father!=largest){
  14.             swap(nums[father],nums[largest]);
  15.             maxHeapDown(nums,largest,heapSize);
  16.         }
  17.     }
  18.     void buildHeap(vector<int>& nums){
  19.         for(int i=nums.size()/2;i>=0;i--){
  20.             maxHeapDown(nums,i,nums.size());
  21.         }
  22.     }
  23.     int findKthLargest(vector<int>& nums, int k) {
  24.         buildHeap(nums);
  25.         int size = nums.size();
  26.         for(int i=0;i<k-1;i++){
  27.             swap(nums[0],nums[size-1]);
  28.             size--;
  29.             maxHeapDown(nums,0,size);
  30.         }    
  31.         return nums[0];
  32.     }
  33. };

快速排序

快速排序找第k大。

  1. class Solution {
  2. public:
  3.     int partition(vector<int>& nums,int l,int r){
  4.         int x = nums[r];
  5.         int i = l;
  6.         for(int j=l;j<r;j++){
  7.             if(nums[j]<x){
  8.                 swap(nums[i++],nums[j]);
  9.             }
  10.         }
  11.         swap(nums[i],nums[r]);
  12.         return i;
  13.     }
  15.     int quickSelect(vector<int>& nums,int l,int r,int index){
  16.         // index的出现保证了其肯定不会出现l>r的情况。
  17.         int mid = partition(nums,l,r);
  18.         if(mid==index){
  19.             return nums[mid];
  20.         } else if(mid<index){ //mid+1<=index<=r
  21.             return quickSelect(nums,mid+1,r,index);
  22.         } else{  //mid-1>=index>=l
  23.             return quickSelect(nums,l,mid-1,index);
  24.         }
  25.     }
  27.     int findKthLargest(vector<int>& nums, int k) {
  28.         int n = nums.size();
  29.         return quickSelect(nums,0,n-1,n-k);
  30.     }
  31. };