leetcode 215. TopK的四种解法

一时失言乱红尘 2022-12-22 00:52 100阅读 0赞

leetcode链接：[数组中的第K个最大元素][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 ≤` 数组的长度。

### 思路分析 ###

这是一道非常经典的题目，在[LeetcodeTop][]中出现频率更是高居第一！

#### 思路一：直接排序 ####

最简答的思路当然是直接排序，当然在刷题时候可以这样，但面试时候面试官肯定不会让你使用`STL`自带的排序。

class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            if(nums.empty())
                return 0;
            std::sort(nums.begin(), nums.end());
            return nums[nums.size() - k];
        }
    
    };

#### 思路二：小根堆 ####

我们可以使用堆的方式来解决这道题目。`std::make_heap`将`vector`的`[start, end)`范围进行堆排序，默认使用`less<int>`, 即大根堆，最大元素放在第一个。

class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            int res = 0;
            vector<int> tmp_heap(k, 0);
            if(!k)
                return res;
            for(int i = 0; i < k; i++)
                tmp_heap[i] = nums[i];
            
            std::make_heap(tmp_heap.begin(), tmp_heap.end(), greater<int>());
    
            for(int i = k; i< nums.size(); i++)
            {
                res = nums[i];
                if(res > tmp_heap[0])
                {
                    swap(tmp_heap[0],  tmp_heap[k - 1]);
                    tmp_heap.pop_back();
                    tmp_heap.push_back(res);
                    std::make_heap(tmp_heap.begin(), tmp_heap.end(), greater<int>());
                }
            }
            return tmp_heap[0];
        }
    
    };

#### 思路三：优先队列 ####

这个思路其实和上面一样，只是换了一个数据结构。

class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            int res = 0;
            if(nums.empty())
                return res;
            priority_queue<int, vector<int>, greater<int> > que;
            for(auto &i: nums)
            {
                que.push(i);
                if(que.size() > k)
                    que.pop();
            }
            return que.top();
        }
    };

#### 思路四：快速排序 ####

这里思路可以看我[C++快速排序实现][C]，就是把`STL`自带的排序替换为手写的快排。

class Solution {
    public:
        int partition(vector<int> &vi, int l, int r) {
            int k = l, pivot = vi[r];
            for (int i = l; i < r; ++i)
                if (vi[i] <= pivot) swap(vi[i], vi[k++]);
            swap(vi[k], vi[r]);
            return k;
        }
        void quicksort(vector<int> &vi, int l, int r) {
            if (l < r) {
                int pivot = partition(vi, l, r);
                quicksort(vi, l, pivot-1);
                quicksort(vi, pivot+1, r);
            }
        }
        int findKthLargest(vector<int>& nums, int k) {
            int res = 0;
            if(nums.empty())
                return res;
            int n = nums.size();
            quicksort(nums, 0, n - 1);
            return nums[n - k]; 
        }
    };

[K]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
[LeetcodeTop]: https://codetop.cc/
[C]: https://blog.csdn.net/xiangxianghehe/article/details/82458589