LeetCode-17day:堆

堆经典题目总结（C++实现）

堆是一种特殊的完全二叉树，广泛应用于优先队列、快速选择等问题。本文总结了三道经典的堆问题，帮助你更好地理解和掌握堆的应用。

🟢 1. 数组中的第 K 个最大元素（Kth Largest Element in an Array）

📄 题目描述：

给定一个整数数组 nums 和一个正整数 k，找出数组中的第 k 个最大元素。

🧠 解题思路（简洁版）

• 快速选择算法：
  • 使用快速排序的分区思想，选择第 k 小的元素。
  • 选择一个分区点，将数组分为两部分。
  • 若 k 小于分区点索引，则递归左半部分；否则递归右半部分。

⏱️ 复杂度分析

• 时间复杂度：O(n)，平均情况下线性时间复杂度。
• 空间复杂度：O(1)，原地操作。

✅ C++ 实现

class Solution {
public:
    int quickselect(vector<int>& nums, int l, int r, int k) {
        if (l == r) return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < partition);
            do j--; while (nums[j] > partition);
            if (i < j) swap(nums[i], nums[j]);
        }
        if (k <= j) return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return quickselect(nums, 0, n - 1, n - k);
    }
};

🟢 2. 前 K 个高频元素（Top K Frequent Elements）

📄 题目描述：

给定一个整数数组 nums 和一个正整数 k，找出数组中出现频率最高的 k 个元素。

🧠 解题思路（简洁版）

• 哈希表 + 优先队列：
  • 使用哈希表统计每个数字的出现次数。
  • 使用大小为 k 的小顶堆（优先队列）维护出现次数最多的 k 个数字。
  • 遍历哈希表，若当前数字的出现次数大于堆顶，则替换堆顶。
  • 最终堆中的数字即为结果。

⏱️ 复杂度分析

• 时间复杂度：O(n log k)，其中 n 为数组长度。
• 空间复杂度：O(n)，哈希表和优先队列。

✅ C++ 实现

class Solution {
public:
    static bool cmp(pair<int, int>& m, pair<int, int>& n) {
        return m.second > n.second;
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> occurrences;
        for (auto& v : nums) {
            occurrences[v]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);

        for (auto& [num, count] : occurrences) {
            if (q.size() == k) {
                if (q.top().second < count) {
                    q.pop();
                    q.emplace(num, count);
                }
            } else {
                q.emplace(num, count);
            }
        }

        vector<int> ret;
        while (!q.empty()) {
            ret.emplace_back(q.top().first);
            q.pop();
        }
        return ret;
    }
};

🟢 3. 数据流的中位数（Find Median from Data Stream）

📄 题目描述：

设计一个数据结构，支持以下两种操作：

• void addNum(int num)：向数据流中添加一个整数。
• double findMedian()：返回数据流的中位数。

🧠 解题思路（简洁版）

• 双优先队列：
  • 使用两个优先队列（一个大顶堆 queMin，一个小顶堆 queMax）维护数据。
  • queMin 存储较小的一半数据，queMax 存储较大的一半数据。
  • 添加数字时，根据大小选择合适的堆，并调整堆的大小平衡。
  • 求中位数时，根据堆的大小关系返回结果。

⏱️ 复杂度分析

• 时间复杂度：O(log n)，每次插入和调整堆的时间复杂度。
• 空间复杂度：O(n)，存储所有数据。

✅ C++ 实现

class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> queMin;
    priority_queue<int, vector<int>, greater<int>> queMax;

    MedianFinder() {}

    void addNum(int num) {
        if (queMin.empty() || num <= queMin.top()) {
            queMin.push(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.push(queMin.top());
                queMin.pop();
            }
        } else {
            queMax.push(num);
            if (queMax.size() > queMin.size()) {
                queMin.push(queMax.top());
                queMax.pop();
            }
        }
    }

    double findMedian() {
        if (queMin.size() > queMax.size()) {
            return queMin.top();
        }
        return (queMin.top() + queMax.top()) / 2.0;
    }
};

📌 总结

希望本文对你有所帮助！如果你还有其他问题，欢迎继续提问。