leetcode-215 Kth Largest Element in an Array

本文主要是介绍leetcode-215 Kth Largest Element in an Array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode上一直没有这个题，感到很沮丧，今天终于出来了，方法有很多种

堆排序：一次AC很开心，也有用C++中的priority_queue<int, std::vector<int>, std::greater<int>>模拟堆的

<span style="font-family:Microsoft YaHei;font-size:14px;">class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int len = nums.size();if(len <= 0) return -1;for(int i = k / 2 - 1; i >= 0; i--){heapAdjust(nums,i,k);}for(int j = k; j < len; j++){if(nums[j] <= nums[0]) continue;int tmp = nums[j];nums[j] = nums[0];nums[0] = tmp;heapAdjust(nums,0,k);}return nums[0];}void  heapAdjust(vector<int> &nums,int i,int len){int tmp,nchild;for(tmp = nums[i]; 2 * i + 1 < len; i = nchild){nchild = 2 * i + 1;if( (nchild + 1 < len) && (nums[nchild] > nums[nchild+1]) ) nchild = nchild + 1;if(tmp > nums[nchild]){nums[i] = nums[nchild];nums[nchild] = tmp;}else break;}}
};</span>

快排思想

<span style="font-family:Microsoft YaHei;font-size:14px;">class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int len = nums.size();if(len <= 0) return -1;return helper(nums,k-1,0,len-1);}int helper(vector<int> &nums,int index,int start,int end){int low = start,high = end;int privotkey = nums[start];while(low < high){while(low < high && nums[high] <= privotkey) high--;if(low < high) nums[low++] = nums[high];while(low < high && nums[low] >= privotkey) low++;if(low < high) nums[high--] = nums[low];}nums[low] = privotkey;if(low == index)return nums[low];else if(low < index){return helper(nums,index,low+1,end);}else if(low > index){return helper(nums,index,start,low-1);}}};</span>

这篇关于leetcode-215 Kth Largest Element in an Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---