215. 数组中的第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
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

知识点

查找，快速排序

Qiang的思路

该题通过快速排序的partition实现。

class Solution {
public:
    int partition(vector<int>& nums, int i, int j){
        int a=nums[i];
        while(i<j){
            while(i<j && nums[j]<=a)j--;
            if(i<j)nums[i]=nums[j];
            while(i<j && nums[i]>a)i++;
            if(i<j)nums[j]=nums[i];
        }
        nums[i]=a;
        return i;
    }
    
    int search(vector<int>& nums, int i, int j, int k){
        int pos=partition(nums, i, j);
        if(pos+1==k)
            return nums[pos];
        if(pos+1>k)
            return search(nums, i, pos-1, k);
        return search(nums, pos+1, j, k);
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        return search(nums, 0, nums.size()-1, k);
    }
};

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。