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.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array‘s length.
题目大意：求一个未排序数组的第k大的数。
思路：
1、直接排序，时间复杂度：O(nlogn)
2、利用优先队列，维持一个大小为k的堆。时间复杂度：O(nlogk）
3、利用快排思想，时间复杂度：O(n)
C++代码：
1 class Solution { 2 //划分函数，返回的数的索引值对应最终排序后的位置 3 int partition(vector<int> &nums, int left, int right) { 4 int p = nums[left]; 5 while (left < right) { 6 while (left < right && nums[right] >= p) right--; 7 nums[left] = nums[right]; 8 while (left < right && nums[left] <= p) left++; 9 nums[right] = nums[left]; 10 } 11 nums[left] = p; 12 return left; 13 } 14 public: 15 int findKthLargest(vector<int>& nums, int k) { 16 int l = 0, r = nums.size() - 1; 17 while (l < r) { 18 int p = partition(nums, l, r); 19 if (p + k == nums.size()) { //满足这个条件表明p指向的位置是第k大的数 20 return nums[p]; 21 } 22 if (p + k < nums.size()) //这个时候只需要排序p后半部分的数组即可找到最终的第k大数 23 l = p + 1; 24 else //此时只需要排序p前半部分 25 r = p - 1; 26 } 27 return nums[nums.size() - k]; 28 } 29 };
leetcode 215. Kth Largest Element in an Array
原文：https://www.cnblogs.com/qinduanyinghua/p/12146625.html