大厂算法HOT100题——数组中的第K个最大元素

由于最近实在是太闲了，所以准备把大厂算法HOT100题刷一遍，持续更新

数组中的第K个最大元素

LeetCode原题连接：数组中的第K个最大元素

---

题意：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

思路一：快速排序

手写快排，返回nums[k-1]即可

三分钟学会快速排序（图示讲解，附代码，通俗易懂）

class Solution {
public:
    void quick_sort(vector<int> &nums,int l,int r)
    {
        if(l>=r) return ;
        int x=nums[(l+r)/2],i=l-1,j=r+1;
        while(i<j)
        {
            do i++; while(nums[i]>x);
            do j--; while(nums[j]<x);
            if(i<j) swap(nums[i],nums[j]);
        }
        quick_sort(nums,l,j),quick_sort(nums,j+1,r);        
    }
    int findKthLargest(vector<int>& nums, int k) {
        quick_sort(nums,0,nums.size()-1);
        return nums[k-1];
    }
};

思路二：优化后的快排算法

该优化基于以下原理：

• 假若左边数字的个数大于等于k，那么要找的值必在左边，因此只需对左边进行递归排序
• 假若左边数字的个数小于等于k，那么要找的值必在右边，因此只需对右边进行递归排序

因此，可以将两次的quick_sort调用优化为一次，从而降低栈内存的使用率

具体可以参考：

对快速排序进行尾递归优化

class Solution {
public:
    int quick_sort(vector<int>& nums,int l,int r,int k)
    {
        if(l==r) return nums[k];
        int x=nums[(l+r)/2],i=l-1,j=r+1;
        while(i<j)
        {
            do i++;while(nums[i]>x);
            do j--;while(nums[j]<x);
            if(i<j) swap(nums[i],nums[j]);
        }
        //int sum=j-l+1;
        if(k<=j) quick_sort(nums,l,j,k);
        else quick_sort(nums,j+1,r,k);
        return nums[k];
    }
    int findKthLargest(vector<int>& nums, int k) {
        return quick_sort(nums,0,nums.size()-1,k-1);
        
    }
};

思路三：借助priority_queue

维护一个大小为k的小根堆，遍历数组nums中所有元素之后，q.top()即为所求

算法复杂度：$O(nlog(k))$

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> q;
        for(auto x:nums)
        {
            q.push(x);
            if(q.size()>k) q.pop();
        }
        return q.top();
    }
};