215数组中的第K个最大元素

题目描述

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

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

问题分析

• 暴力解法
  直接排序，取所指定位置的元素
• 构建小顶堆，保持为K

解题思路1

暴力解法

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        int result = 0;
        int len = nums.size();
        if (len == 0 || k > len)
        {
            return 0;
        }
        sort(nums.begin(), nums.end());
        result = nums[len- k];
        return result;
    }
};

解题思路2

小顶堆

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        int result = 0;
        int len = nums.size();
        
        if (len == 0 || k > len)
        {
            return 0;
        }
        priority_queue<int, vector<int>, greater<int>> store;
        for (int i = 0; i < len; ++i)
        {
            store.push(nums[i]);
            if (int(store.size()) > k)
            {
                store.pop();
            }
        }
        result = store.top();
        return result;
    }
};