首页 > 代码库 > leetcode-Kth Largest Element in an Array-215

leetcode-Kth Largest Element in an Array-215

输入一个数组,求第k大的数

利用快排,因为快排的每一轮递归使一个元素归位,所以判断当前归位的元素是否是第k个,若是,返回

 1 class Solution { 2 public: 3     void quick(vector<int> &a,int low,int high,int k){ 4         int i=low,j=high-1; 5         int tmp=a[i]; 6         while(i<j){ 7             while(i<j&&a[j]>=tmp) j--; 8             a[i]=a[j]; 9             while(i<j&&a[i]<=tmp) i++;10             a[j]=a[i];11         }12         a[i]=tmp;13         if(i==a.size()-k) return;14         if(i>low) quick(a,low,i,k);15         if(i+1<high) quick(a,i+1,high,k);16     }17     int findKthLargest(vector<int>& nums, int k) {18         if(nums.size()<k) return -1;19         quick(nums,0,nums.size(),k);20         return nums[nums.size()-k];21     }22 };

 

leetcode-Kth Largest Element in an Array-215