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<int>& 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<k;n++){
            if(nums[n]==nums[n-1]) n--;
        }
        return nums[n-1];
    }
};

解法二，快速排序法A：

int Partition(vector<int>& nums,int left,int right,int k){
        int pivo=nums[left];//选取nums最左端元素作为比较元素
        int position=left,j=right;
        while(position<j){
            while(nums[j]>=pivo && position<j) j--;//向左寻找直至发现某元素值大于pivo
            nums[position] = nums[j];//将nums[j]值暂存
            while(nums[position]<=pivo && position<j) position++;//向右寻找直至发现某元素值小于pivo
            nums[j] = nums[position];//此时j右边的值都大于nums[j],position左边的值都小于nums[position]
        }
        nums[position] = pivo;//此时position右边的值都大于nums[position],position左边的值都小于nums[position]
        return position;
    }

int findKthLargest(vector<int>& 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<target)
                left = index + 1;
            else
                right = index - 1;
    }
}

快速排序法改进B：

为了应对如数组全是倒序或几乎所有元素都重复的极端情况（此时复杂度为O(n2)），要对A方法进行改进，即每次选取比较点pivo时要做到随机选取，具体来说就是将nums[left]与nums[random]进行交换，其中random是位于left到right区间的随机正整数

int Partition(vector<int>& nums,int left,int right,int k){
        if(left<right){
            swap(nums[left],nums[left+rand() % (right-left+1)]);//选取[left,right]的随机元素与nums[left]交换，以达到随机选取比较点的目的
        }
        int pivo=nums[left];
        int position=left,j=right;
        while(position<j){
            while(nums[j]>=pivo && position<j) j--;
            nums[position] = nums[j];
            while(nums[position]<=pivo && position<j) position++;
            nums[j] = nums[position];
        }
        nums[position] = pivo;
        return position;
    }

int findKthLargest(vector<int>& 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<target)
                left = index + 1;
            else
                right = index - 1;
    }
}

解法三，利用优先级队列：

可以利用优先级队列，把 len 个元素都放入一个最大堆中，然后再 pop() 出 k - 1 个元素，选取此时最大堆的堆顶元素，也就是数组中的第 k 个最大元素。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> 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();
    }
};

leetcode215. 数组中的第K个最大元素

原文：https://www.cnblogs.com/due-east/p/14808491.html