LeetCode题解——Kth Largest Element in an Array

本文主要是介绍LeetCode题解——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:
//方法一：建立一个堆维护k个最大的数,没有必要，因为只需要第k大，而不需要前k大的数
//方法二：partition and findKthLargest.//利用快排的思想int findKthLargest(vector<int>& nums, int k) {//if(k<1||k>nums.size()) return 0;int begin = 0, end = nums.size()-1;while(true){int index = partition(nums,begin,end);if(index==nums.size()-k) return nums[index];else if(index<nums.size()-k) begin = index+1;else end = index-1;}}int partition(vector<int>& nums,int begin,int end){// if(!nums.size() || begin<0 || end<0 || end>nums.size()-1) //     throw("Invalid Parameters");if(end==begin) return begin;int idx = rand()%(end-begin)+begin;swap(&nums[idx], &nums[end]);int small = begin-1;for(idx = begin; idx<end; ++idx){if(nums[idx]<nums[end]){small++;if(small!=idx) swap(&nums[idx],&nums[small]);}}++small;swap(&nums[small],&nums[end]);return small;}void swap(int*x,int*y){int temp;temp=*x;*x=*y;*y=temp;}
};

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

---