LeetCode - 解题笔记 - 215 - Kth Largest Element in an Array

Solution 1

本题有时间限制，也就是需要在线性时间内完成至少部分排序和查找工作。

第一个思路：不稳定的快速排序。提交了确实能过……

• 时间复杂度： $O(N)$，其中$N$为输入数组的长度，排序的最佳实现可以达到线性复杂度，但是实际并不稳定。
• 空间复杂度： $O(\log N)$，其中$N$为输入数组的长度，快速排序过程中的函数递归调用之占用

class Solution {
   
public:
    int findKthLargest(vector<int>& nums, int k) {
   
        sort(nums.begin(), nums.end(), greater<int>(
1
2
3
4
5