当前位置： 首页 > article >正文

优先队列（典型算法思想）—— OJ例题算法解析思路

article 2025/2/26 2:59:19

目录

一、1046. 最后一块石头的重量 - 力扣（LeetCode）

算法代码： 

代码思路

使用优先队列（大根堆）

将所有石头放入堆中

模拟碰撞过程

返回最后的重量

代码解析

时间复杂度

示例

输入

输出

二、703. 数据流中的第 K 大元素 - 力扣（LeetCode） 

算法代码： 

代码思路

使用小根堆（最小堆）

构造函数

添加元素的方法

代码解析

时间复杂度

示例

输入

输出

三、692. 前K个高频单词 - 力扣（LeetCode）

算法代码： 

代码思路

统计单词频率

自定义比较器

维护小根堆

提取结果

代码解析

时间复杂度

示例

输入

输出

四、295. 数据流的中位数 - 力扣（LeetCode） 

算法代码： 

代码思路

使用两个堆

添加数字

计算中位数

代码解析

时间复杂度

示例

使用示例

输出

一、1046. 最后一块石头的重量 - 力扣（LeetCode）

算法代码： 

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        // 1. 创建⼀个⼤根堆
        priority_queue<int> heap;
        // 2. 将所有元素丢进这个堆⾥⾯
        for (auto x : stones)
            heap.push(x);
        // 3. 模拟这个过程
        while (heap.size() > 1) {
            int a = heap.top();
            heap.pop();
            int b = heap.top();
            heap.pop();
            if (a > b)
                heap.push(a - b);
        }
        return heap.size() ? heap.top() : 0;
    }
};

代码思路

  1. 使用优先队列（大根堆）

    • 利用 priority_queue 来模拟石头的碰撞过程。大根堆可以帮助我们快速找到当前最重的两块石头。

  2. 将所有石头放入堆中

    • 通过循环将给定的石头重量插入到优先队列中。这样，最重的石头将始终位于堆的顶部。

  3. 模拟碰撞过程

    • 使用 while 循环，当堆中石头的数量大于 1 时，继续进行碰撞。

      • 从堆中取出两块最重的石头（a 和 b）。

      • 如果 a 和 b 不相等，将它们的重量差（a - b）重新放回堆中。

      • 如果它们相等，则两块石头都被摧毁，不会被放回堆中。

  4. 返回最后的重量

    • 当堆中只剩下一个石头时，返回这个石头的重量；如果没有石头剩下，则返回 0。

代码解析

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        // 1. 创建一个大根堆
        priority_queue<int> heap;
        // 2. 将所有元素丢进这个堆里面
        for (auto x : stones)
            heap.push(x);
        // 3. 模拟这个过程
        while (heap.size() > 1) {
            int a = heap.top(); // 取出最大元素
            heap.pop();         // 移除最大元素
            int b = heap.top(); // 取出第二大元素
            heap.pop();         // 移除第二大元素
            if (a > b)         // 如果不相等，进队差值
                heap.push(a - b);
        }
        return heap.size() ? heap.top() : 0; // 返回最后的重量
    }
};

时间复杂度

  • 将所有石头插入到优先队列的时间复杂度是 O(n log n)，其中 n 是石头的数量。

  • 每次从堆中取出两个元素并可能插入一个元素的操作时间复杂度是 O(log n)，这在最坏情况下会进行 n 次，因此整体最坏的时间复杂度为 O(n log n)。

示例

输入

vector<int> stones = {2, 7, 4, 1, 8, 1};
Solution sol;
cout << sol.lastStoneWeight(stones); // 输出：1

输出

  • 在这个例子中，最终剩下的石头重量是 1。

这种方法通过使用大根堆有效地处理了石头碰撞的问题，能够快速找到最重的石头并进行处理。

二、703. 数据流中的第 K 大元素 - 力扣（LeetCode） 

算法代码： 

class KthLargest {
    // 创建⼀个⼤⼩为 k 的⼩跟堆
    priority_queue<int, vector<int>, greater<int>> heap;
    int _k;

public:
    KthLargest(int k, vector<int>& nums) {
        _k = k;
        for (auto x : nums) {
            heap.push(x);
            if (heap.size() > _k)
                heap.pop();
        }
    }

    int add(int val) {
        heap.push(val);
        if (heap.size() > _k)
            heap.pop();
        return heap.top();
    }
};
/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

代码思路

  1. 使用小根堆（最小堆）

    • 利用 priority_queue 来创建一个小根堆，堆中最多保留 k 个元素。小根堆的特性是堆顶（即顶部元素）是当前堆中最小的元素。

  2. 构造函数

    • KthLargest(int k, vector<int>& nums) 构造函数接受一个整数 k 和一个整数数组 nums。

    • 将数组中的元素依次插入到小根堆中，对于每个插入的元素，如果堆的大小超过 k，则移除堆顶元素（即最小元素）。

    • 这样在堆中始终保持 k 个最大的元素，堆顶元素即为第 k 大的元素。

  3. 添加元素的方法

    • int add(int val) 方法用于向数据结构中添加一个新元素 val。

    • 将新元素插入堆中，并再次检查堆的大小。如果堆的大小超过 k，则移除堆顶元素。

    • 返回当前堆顶元素，这个元素就是当前的第 k 大元素。

代码解析

class KthLargest {
    // 创建一个大小为 k 的小根堆
    priority_queue<int, vector<int>, greater<int>> heap;
    int _k;

public:
    KthLargest(int k, vector<int>& nums) {
        _k = k; // 初始化 k
        for (auto x : nums) {
            heap.push(x); // 将元素插入堆中
            if (heap.size() > _k) // 如果堆的大小超过 k
                heap.pop(); // 移除堆顶元素
        }
    }

    int add(int val) {
        heap.push(val); // 插入新元素
        if (heap.size() > _k) // 如果堆的大小超过 k
            heap.pop(); // 移除堆顶元素
        return heap.top(); // 返回当前的第 k 大元素
    }
};
/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

时间复杂度

  • 在构造函数中，插入 n 个元素到堆中的时间复杂度为 O(n log k)，因为每次插入堆的操作是 O(log k)。

  • 在 add 方法中，每次插入和检索操作的时间复杂度为 O(log k)。

  • 整个算法的空间复杂度为 O(k)，因为堆中最多存储 k 个元素。

示例

输入

int k = 3;
vector<int> nums = {4, 5, 8, 2};
KthLargest* obj = new KthLargest(k, nums);
int param_1 = obj->add(3); // 返回 4
int param_2 = obj->add(5); // 返回 5
int param_3 = obj->add(10); // 返回 5
int param_4 = obj->add(9); // 返回 8
int param_5 = obj->add(4); // 返回 8

输出

  • param_1 为 4，说明现在的第 3 大元素是 4。

  • param_2 为 5，说明现在的第 3 大元素是 5。

  • param_3 为 5，依然是第 3 大元素。

  • param_4 为 8，说明现在的第 3 大元素是 8。

  • param_5 也为 8，依然是第 3 大元素。

这种实现方式通过小根堆高效地维护了动态数组中第 k 大元素的状态，适合于需要频繁添加元素并查询第 k 大元素的场景。

 

三、692. 前K个高频单词 - 力扣（LeetCode）

算法代码： 

class Solution {
    typedef pair<string, int> PSI;
    struct cmp {
        bool operator()(const PSI& a, const PSI& b) {
            if (a.second == b.second) // 频次相同，字典序按照⼤根堆的⽅式排列
            {
                return a.first < b.first;
            }
            return a.second > b.second;
        }
    };

public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 1. 统计⼀下每⼀个单词的频次
        unordered_map<string, int> hash;
        for (auto& s : words)
            hash[s]++;
        // 2. 创建⼀个⼤⼩为 k 的堆
        priority_queue<PSI, vector<PSI>, cmp> heap;
        // 3. TopK 的主逻辑
        for (auto& psi : hash) {
            heap.push(psi);
            if (heap.size() > k)
                heap.pop();
        }
        // 4. 提取结果
        vector<string> ret(k);
        for (int i = k - 1; i >= 0; i--) {
            ret[i] = heap.top().first;
            heap.pop();
        }
        return ret;
    }
};

代码思路

  1. 统计单词频率

    • 使用 unordered_map<string, int> 来统计每个单词在输入数组中的出现次数。

  2. 自定义比较器

    • 定义一个结构体 cmp，用于优先队列中元素的比较。这个比较器实现了以下逻辑：

      • 如果两个单词的频率相同，则按字典序进行排序（按字母逆序，即较大的字母排在前面，形成一个大根堆）。

      • 否则，频率较高的单词应排在前面（形成一个小根堆）。

  3. 维护小根堆

    • 使用 priority_queue 来创建一个小根堆，存储单词及其频率。

    • 遍历频率统计的哈希表，将每个单词及其频率插入堆中。如果堆的大小超过 k，则弹出堆顶元素，从而保持堆中只包含 k 个频率最高的单词。

  4. 提取结果

    • 创建一个结果向量 ret，用于存储最终的 k 个单词。

    • 由于我们在维护小根堆时，频率最高的单词在堆底，因此提取时需要从堆中依次弹出元素，并逆序填入结果向量。

代码解析

class Solution {
    typedef pair<string, int> PSI; // 定义一个字符串-频率对
    struct cmp {
        bool operator()(const PSI& a, const PSI& b) {
            if (a.second == b.second) // 如果频率相同，按字典序比较
            {
                return a.first < b.first; // 字典序：较大的字母排在前面
            }
            return a.second > b.second; // 否则按频率比较
        }
    };

public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 1. 统计每一个单词的频次
        unordered_map<string, int> hash;
        for (auto& s : words)
            hash[s]++;
        
        // 2. 创建一个大小为 k 的小根堆
        priority_queue<PSI, vector<PSI>, cmp> heap;
        
        // 3. TopK 的主逻辑
        for (auto& psi : hash) {
            heap.push(psi); // 插入单词频率对
            if (heap.size() > k) // 如果堆的大小超过 k
                heap.pop(); // 移除堆顶元素
        }
        
        // 4. 提取结果
        vector<string> ret(k); // 结果向量
        for (int i = k - 1; i >= 0; i--) {
            ret[i] = heap.top().first; // 获取堆顶元素的单词
            heap.pop(); // 移除堆顶元素
        }
        return ret; // 返回结果
    }
};

时间复杂度

  • 统计频率的时间复杂度为 O(n)，其中 n 是单词数组的长度。

  • 在最坏情况下，当哈希表中有 n 个不同单词时，维护小根堆的时间复杂度为 O(n log k)，因为每次插入和删除堆顶的操作都是 O(log k)。

  • 因此，整体时间复杂度为 O(n log k)。

示例

输入

vector<string> words = {"i", "love", "leetcode", "i", "love", "coding"};
int k = 2;
Solution sol;
vector<string> result = sol.topKFrequent(words, k); // 返回 {"i", "love"}

输出

  • result 包含了出现频率最高的两个单词 “i” 和 "love"。

这种实现方式通过使用哈希表和小根堆有效地解决了查找第 k 个频繁单词的问题，能够快速处理数据并返回结果。

四、295. 数据流的中位数 - 力扣（LeetCode） 

算法代码： 

class MedianFinder {
    priority_queue<int> left;                             // ⼤根堆
    priority_queue<int, vector<int>, greater<int>> right; // ⼩根堆
public:
    MedianFinder() {}

    void addNum(int num) {
        // 分类讨论即可
        if (left.size() == right.size()) // 左右两个堆的元素个数相同
        {
            if (left.empty() || num <= left.top()) // 放 left ⾥⾯
            {
                left.push(num);
            } else {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        } else {
            if (num <= left.top()) {
                left.push(num);
                right.push(left.top());
                left.pop();
            } else {
                right.push(num);
            }
        }
    }

    double findMedian() {
        if (left.size() == right.size())
            return (left.top() + right.top()) / 2.0;
        else
            return left.top();
    }
};
/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

代码思路

  1. 使用两个堆

    • 大根堆 (left)：存储较小的一半数字，堆顶是这部分数字的最大值。

    • 小根堆 (right)：存储较大的一半数字，堆顶是这部分数字的最小值。

  2. 添加数字

    • 当添加一个新的数字时，根据当前两个堆的大小和新数字的值决定将其放入哪个堆：

      • 如果两个堆的大小相同，且新数字小于等于大根堆的堆顶，则将其放入大根堆；否则，将其放入小根堆，然后将小根堆的堆顶元素移到大根堆中。

      • 如果大根堆的大小大于小根堆，且新数字小于等于大根堆的堆顶，则将其放入大根堆，并将其堆顶元素移到小根堆；否则，直接放入小根堆。

    • 这样可以保证大根堆的元素总是小于等于小根堆的元素，并且大根堆的大小要么等于小根堆的大小，要么大一个元素。

  3. 计算中位数

    • 如果两个堆的大小相等，则中位数为两个堆顶元素的平均值。

    • 如果大根堆的大小大于小根堆，则中位数为大根堆的堆顶元素。

 

代码解析

class MedianFinder {
    priority_queue<int> left;                             // 大根堆
    priority_queue<int, vector<int>, greater<int>> right; // 小根堆
    
public:
    MedianFinder() {}

    void addNum(int num) {
        // 分类讨论
        if (left.size() == right.size()) // 左右两个堆的元素个数相同
        {
            if (left.empty() || num <= left.top()) // 放入大根堆
            {
                left.push(num);
            } else { // 放入小根堆
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        } else { // 大根堆的元素个数大于小根堆
            if (num <= left.top()) {
                left.push(num);
                right.push(left.top());
                left.pop();
            } else {
                right.push(num);
            }
        }
    }

    double findMedian() {
        if (left.size() == right.size())
            return (left.top() + right.top()) / 2.0; // 两堆大小相同
        else
            return left.top(); // 大根堆较多
    }
};
/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

时间复杂度

  • addNum 方法的时间复杂度是 O(log n)，因为每次插入堆的时间复杂度为 O(log n)。

  • findMedian 方法的时间复杂度是 O(1)，因为只需返回堆顶元素。

  • 整体的空间复杂度是 O(n)，存储所有的数字。

示例

使用示例

MedianFinder* obj = new MedianFinder();
obj->addNum(1);
obj->addNum(2);
double median1 = obj->findMedian(); // 返回 1.5
obj->addNum(3);
double median2 = obj->findMedian(); // 返回 2.0

输出

  • 第一次调用 findMedian() 时，返回 1.5，因为当前的数字是 1 和 2。

  • 第二次调用时，返回 2.0，因为当前的数字是 1、2 和 3。

这种实现方式通过使用两个堆来高效地维护动态数据集的中位数，适用于需要频繁添加数字并查询中位数的场景。


http://www.kler.cn/a/553083.html

相关文章：

  • 打破限制！自定义 Hooks 如何提升 React 组件的灵活性
  • 用户坐标系（ucs）与系统坐标系（wcs）的转换详解——CAD c#二次开发
  • 【AI工程实践】阅文集团：NLP在网络文学领域的应用
  • Java Spring boot 篇：常用注解
  • 数智驱动：医学编程与建模技术在智慧医院AI建设中的创新与变革
  • floodfill算法系列一＞衣橱整理
  • 4.7 模型训练基类Trainer：Hugging Face工业级训练引擎深度剖析
  • 安装mmdet3d报错【fatal error: spconv/maxpool.h: No such file or directory】
  • `fi` 是 Bash 脚本中用来结束 `if` 条件语句块的关键字
  • firefox升级后如何恢复收藏夹和密码的问题
  • SPO（Self-Supervised Prompt Optimization）自我监督Prompt提示优化的全景指南
  • 机器人路径规划 | 基于极光PLO优化算法的机器人三维路径规划Matlab代码
  • 【嵌入式Linux应用开发基础】特殊进程
  • 机试刷题_矩阵的最小路径和【python】
  • 7.【线性代数】——求解Ax=0，主列和自由列
  • Spring Cloud环境搭建
  • 【数据结构】队列(Queue)
  • 前端需要学习 Docker 吗？
  • 【Elasticsearch】近实时搜索与刷新机制
  • Dockerfile制作镜像示例 X86版本