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大的数。用小堆去维护
这题几年前做过...
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int,vector<int>, greater<int>> q; for (int i = 0; i < nums.size(); ++i) { if (q.empty()) q.push(nums[i]); else { int x = q.top(); if (q.size() < k) q.push(nums[i]); else { if (nums[i] > x) q.pop(), q.push(nums[i]); } } } if (q.empty()) return 0; return q.top(); } };
leetcode 215. Kth Largest Element in an Array
原文：http://www.cnblogs.com/pk28/p/7424674.html