首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。