Description 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.
解题思路：题目要求出第K大的数，而且是有序数列里的第k个数（假如数列是从大到小排列），这就是说重复的数也计算在内。解题的关键就在于排序上，这道题我采用的是快排的算法将数组排好序，然后再求出第K大的数。程序如下：
class Solution {public: void Qsort(vector<int> & arr,int begin,int end){ if(begin>=end) return; else{ int key=arr[begin]; int last_small=begin; //last_small记录最后一个比选定的key值小的数的位置 int i=begin+1; while(i<=end){ if(arr[i]<=key){ swap(arr[last_small+1],arr[i]); //last_small+1就是比key值大的数的位置 last_small++; //交换后，last_small后移 } i++; } swap(arr[begin],arr[last_small]); //将key值放到正确的位置 Qsort(arr,begin,last_small-1); Qsort(arr,last_small+1,end); }} int findKthLargest(vector<int>& nums, int k) { Qsort(nums,0,nums.size()-1); return nums[nums.size()-k]; }};新闻热点
疑难解答
