首頁 盲人摸象

# 题目

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

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

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

# 暴力求解

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int findKthLargest(vector<int> &nums, int k) {
        int size = nums.size();
        sort(begin(nums), end(nums));
        return nums[size - k];
    }
};
# 大顶堆
调用 priority_queue
class Solution
{
public:
    int findKthLargest(vector<int> &nums, int k)
    {
        priority_queue<int, vector<int>, less<int>> maxHeap;
        for (int x : nums)
            maxHeap.push(x);
        for (int _ = 0; _ < k - 1; _++)
            maxHeap.pop();
        return maxHeap.top();
    }
};
NB solution
class Solution
{
public:
    void shiftDown(vector<int> &nums, int i, int len)
    {
        int root = i;
        while (root < len)
        {
            int tmp = root;
            int left = 2 * root + 1, right = 2 * root + 2;
            if (left < len && nums[root] < nums[left])
            {
                root = left;
            }
            if (right < len && nums[root] < nums[right])
            {
                root = right;
            }
            if (root == tmp)
            {
                break;
            }
            swap(nums[tmp], nums[root]);
        }
    }
    void buildHeap(vector<int> &nums)
    {
        int n = nums.size();
        for (int i = n / 2 - 1; i >= 0; i--)
        {
            shiftDown(nums, i, n);
        }
    }
    int findKthLargest(vector<int> &nums, int k)
    {
        // 构建最大堆
        buildHeap(nums);
        int n = nums.size();
        //pop k-1 个元素
        for (int i = n - 1; i > n - k; i--)
        {
            swap(nums[0], nums[i]);
            shiftDown(nums, 0, i);
        }
        return nums[0];
    }
};
# 优先队列
其内部可以看作是一棵由数组模拟的完全二叉树，对于这棵树的每一个结点来说，自身的优先级不低于左右孩子的优先级，所以其功能就是拿出优先级最大的元素，如何简单使用 C++ 中内置容器 priority_queue ？首先引出头文件 <queue> ，定义一个默认的优先队列（大顶堆） priority_queue<int> que; 即值越大的元素优先级越高先出队。
  • que.size () 元素数量
  • que.push (x) 插入 x
  • que.pop () 删除优先级最高的元素
  • que.top () 访问优先级最高的元素（堆顶元素）
  • que.empty () 判空
对于优先队列的操作，插入删除的时间复杂度为对数级，访问堆顶元素时间复杂度为常数级，所以比较适合动态调整，获得极值。
#include <iostream>
#include <queue>
using namespace std;
// 大顶堆
int main()
{
    priority_queue<int> que;
    que.push(7);
    que.push(5);
    que.push(-2);
    que.push(1);
    que.push(6);
    cout << que.size() << endl;
    while (!que.empty())
    {
        cout << que.top() << " ";
        que.pop();
    }
    cout << endl;
    return 0;
}
如何定义一个小顶堆？优先队列除了第一个数据类型以外，还有其他两个模板参数：底层顺序结构类型（默认是 vector，也可使用 queue 或者 array），第三个参数是一个仿函数，提供优先队列权值比较方法。
priority_queue<int, vector<int>, less<int>> q;    // 大顶堆
priority_queue<int, vector<int>, greater<int>> q; // 小顶堆
其中 greater<int> 和 less<int> 即为仿函数，其中 greater 的实现如下
template <class T>
struct greater : public binary_function<T, T, bool>
{
    bool operator()(const T &x, const T &y) const
    {
        return x > y;
    }
}
#include <iostream>
#include <queue>
using namespace std;
// 小顶堆
int main()
{
    priority_queue<int, vector<int>, greater<int>> que;
    que.push(7);
    que.push(5);
    que.push(-2);
    que.push(1);
    que.push(6);
    cout << que.size() << endl;
    while (!que.empty())
    {
        cout << que.top() << " ";
        que.pop();
    }
    cout << endl;
    return 0;
}
定义一个自定义类型的优先队列
#include <iostream>
#include <queue>
using namespace std;
struct node
{
    int x, y;
    // 重载运算符，重载小于号，若需小根堆，this->x > b.x 即可
    bool operator<(const node &b) const
    {
        return this->x < b.x;
    }
};
int main()
{
    priority_queue<node> que;
    que.push((node){1, 5});
    que.push((node){2, 3});
    que.push((node){9, 4});
    que.push((node){-5, 5});
    while (!que.empty())
    {
        cout << que.top().x << endl;
        que.pop();
    }
    return 0;
}
[root@VM-12-16-centos lab]# ./a.out 
9
2
1
-5