LeetCode *** 215. Kth Largest Element in an Array

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

题目：

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

分析：

堆排序

代码：

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int size=nums.size();for(int i=size-1;i>=0;--i)heapSort(nums,i,size-1);for(int i=0;i<k-1;++i){int tmp=nums[0];nums[0]=nums[size-i-1];nums[size-i-1]=tmp;heapSort(nums,0,size-i-2);}return nums[0];}void heapSort(vector<int>& nums,int start,int end){int parent=start;int childIndex=start*2+1;while(childIndex<end){if(nums[childIndex+1]>nums[childIndex])childIndex++;if(nums[parent]>nums[childIndex])break;int tmp=nums[parent];nums[parent]=nums[childIndex];nums[childIndex]=tmp;parent=childIndex;childIndex=childIndex*2+1;}if(childIndex==end&&nums[childIndex]>nums[parent]){int tmp=nums[parent];nums[parent]=nums[childIndex];nums[childIndex]=tmp;}}};

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

---