leetcode215. 数组中的第K个最大元素
题目描述：
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
解法一，暴力解法：
class Solution {
public:
int findKthLargest(vector& nums, int k) {
long long unsigned int i=1,j=nums.size()-1;
while(j>0){
i = 0;
while(i<=j){
if(nums[i]>nums[i-1]){
swap(nums[i],nums[i-1]);
i++;
}
else{
i++;
}
}
j--;
}
int n;
for(n=1;n
解法二，快速排序法A：
int Partition(vector& nums,int left,int right,int k){
int pivo=nums[left];//选取nums最左端元素作为比较元素
int position=left,j=right;
while(position=pivo && position& nums, int k) {
int left = 0, right = nums.size() - 1;
int target = nums.size() - k;
while(true){
int index=Partition(nums,left,right,k);
if(index==target)
return nums[index];
else if(index
快速排序法改进B：
为了应对如数组全是倒序或几乎所有元素都重复的极端情况（此时复杂度为O(n2)），要对A方法进行改进，即每次选取比较点pivo时要做到随机选取，具体来说就是将nums[left]与nums[random]进行交换，其中random是位于left到right区间的随机正整数
int Partition(vector& nums,int left,int right,int k){
if(left=pivo && position& nums, int k) {
int left = 0, right = nums.size() - 1;
int target = nums.size() - k;
while(true){
int index=Partition(nums,left,right,k);
if(index==target)
return nums[index];
else if(index
解法三，利用优先级队列：
可以利用优先级队列，把 len 个元素都放入一个最大堆中，然后再 pop() 出 k - 1 个元素，选取此时最大堆的堆顶元素，也就是数组中的第 k 个最大元素。
class Solution {
public:
int findKthLargest(vector& nums, int k) {
priority_queue q;//priority_queue是一种C++的container adaptors，默认构成最大堆
for(auto n:nums){
q.push(n);
}
for(int i=nums.size();i>nums.size()-k+1;i--){
q.pop();
}
return q.top();
}
};