优先级队列(堆)

发布于:2024-05-15 ⋅ 阅读:(152) ⋅ 点赞:(0)

目录

leetcode题目

一、数组中两元素的最大乘积

二、最后一块石头的重量

三、数据流中的第 K 大元素

四、前K个高频元素

五、前K个高频单词

六、数据流的中位数

七、有序矩阵中的第K小的元素

八、根据字符出现频率排序


leetcode题目

一、数组中两元素的最大乘积

1464. 数组中两元素的最大乘积 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/maximum-product-of-two-elements-in-an-array/1.题目解析

求数组中最大的两个元素top1, top2, 返回(top1-1)*(top2-1)

2.算法分析

遍历数组,放入优先级队列中,pop出最大的两个元素,求结果即可

3.算法代码

class Solution {
public:
    int maxProduct(vector<int>& nums) 
    {
        priority_queue<int> q;
        for(auto x : nums)
            q.push(x);
        int top1 = q.top();
        q.pop();
        int top2 = q.top();
        q.pop();
        return (top1-1) * (top2-1);
    }
};

二、最后一块石头的重量

1046. 最后一块石头的重量 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/last-stone-weight/description/1.题目解析

每次选取最重的两块石头,两两碰撞,重量小的粉碎,重量大的石头剩余重量为原始重量-重量小的石头的重量,最终如果剩一块石头,就返回该石头的重量;如果没有剩石头,就返回0

2.算法分析

用堆(优先级队列) 模拟即可

3.算法代码

class Solution {
public:
    int lastStoneWeight(vector<int>& stones)
    {
        priority_queue<int> heap; //默认大堆
        for(auto x : stones)
            heap.push(x);
        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() == 1 ? heap.top() : 0;
    }
};

三、数据流中的第 K 大元素

703. 数据流中的第 K 大元素 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/kth-largest-element-in-a-stream/1.题目解析

实现一个类, 返回给定数组的第K大元素(排序之后的)(不断新增数据)

2.算法分析

典型的top-k问题,用优先级队列来解决~

详见博客: 独树一帜的完全二叉树---堆-CSDN博客

3.算法代码

class KthLargest {
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();
    }
private:
    priority_queue<int, vector<int>, greater<int>> heap; //小堆
    int _k;
};

四、前K个高频元素

347. 前 K 个高频元素 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/top-k-frequent-elements/1.题目解析

给定一个数组,返回该数组中出现次数最多的k个元素, 顺序任意

2.算法分析

典型的top-k问题,不过求的不是前K大的元素或前K小的元素,而是求前K个出现次数最多的元素,因此我们先用哈希表绑定每个元素和其出现的次数;然后定义优先级队列, 每个元素类型是pair<int, int> (传仿函数指定比较规则,按照pair中的second也就是元素次数进行比较,由于求的是出现次数最多的k个单词,因此建小堆), 最后从优先级队列中提取结果即可

3.算法代码

class Solution {
public:
    typedef pair<int, int> PII;
    struct cmp
    {
        bool operator()(const PII& p1, const PII& p2)
        {
            return p1.second > p2.second; //小堆比较规则
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        //1.哈希表统计次数
        unordered_map<int, int> hash; //单词-次数
        for(auto& e : nums)
            hash[e]++;

        //2.Top-K的主逻辑
        priority_queue<PII, vector<PII>, cmp> heap;
        for(auto& pii : hash)
        {
            heap.push(pii);
            if(heap.size() > k) heap.pop();
        }

        //3.提取结果
        vector<int> ret(k);
        for(int i = k-1; i >= 0; i--)
        {
            ret[i] = heap.top().first;
            heap.pop();
        }
        return ret;
    }
};

五、前K个高频单词

692. 前K个高频单词 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/top-k-frequent-words/1.题目解析

返回前k个出现次数最多的单词,如果出现频次相同,按照字典序从小到大排列

2.算法分析

同样是top-k问题,但是比较规则有所变化,在priority_queue中传递仿函数指定比较规则即可~

仿函数博客: stack 与 queue 与 priority_queue 与 仿函数 与 模板进阶-CSDN博客

1.哈希表统计单词出现次数

2.创建大小为k的堆

比较规则:

①单词频次不同时,由于频次高的往前排,因此创建小根堆

②单词频次相同时,谁的字典序小谁往前排,因此创建大根堆

3. top-K的主逻辑

4. 提取结果(注意在vector中存放的顺序)

3.算法代码

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.top-k主逻辑
        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;
    }
};

六、数据流的中位数

295. 数据流的中位数 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/find-median-from-data-stream/description/1.题目解析

实现一个类,求数据流的中位数(不断新增数据), 奇数个元素返回中位数,偶数个元素返回中间两个数的平均值

2.算法分析

大小堆维护数据流的中位数

1.当 m == n, 中位数就是两个堆的堆顶元素的平均值

2.当 m == n + 1, 中位数就是大根堆的堆顶元素

细节问题: add()函数, 插入num元素

1. m == n

1.1 num <= x 或 m == 0, 此时进入大根堆,  m == n + 1

1.2 num > x, 进入小根堆, 此时 n = m + 1, 因此我们需要调整, 只需要把小根堆的堆顶元素挪到大根堆的堆顶即可~

2. m == n+1

2.2 num <= x, 此时进入大根堆,  m == n + 2, 因此我们需要调整, 只需要将大根堆的堆顶元素挪到小根堆的堆顶即可~

2.2 num > x, 此时进入小根堆,  m == n

3.算法代码

class MedianFinder {
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();
    }
private:
    priority_queue<int> left; //大根堆
    priority_queue<int, vector<int>, greater<int>> right; //小根堆
};

七、有序矩阵中的第K小的元素

378. 有序矩阵中第 K 小的元素 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/1.题目解析

求矩阵中第K小的元素

2.算法分析

优先级队列

3.算法代码

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) 
    {
        priority_queue<int> heap;
        int m = matrix.size(), n = matrix[0].size();
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                heap.push(matrix[i][j]);
                if(heap.size() > k) heap.pop();
            }
        }
        return heap.top();
    }
};

八、根据字符出现频率排序

451. 根据字符出现频率排序 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/sort-characters-by-frequency/1.题目解析

把出现频率高的字符排在前面, 输出新的字符串

2.算法分析

优先级队列

3.算法代码

class Solution {
    typedef pair<char, int> PCI;
public:
    struct cmp
    {
        bool operator()(const PCI& p1, const PCI& p2)
        {
            return p1.second < p2.second; //大堆
        }
    };

    string frequencySort(string s) 
    {
        //1.哈希表统计频次
        unordered_map<char, int> hash;
        for(auto ch : s)
            hash[ch]++;
        //2.top-k的主逻辑
        priority_queue<PCI, vector<PCI>, cmp> heap;
        for(auto pci : hash)
            heap.push(pci);
        //3.提取结果
        string ret;
        while(!heap.empty())
        {
            auto top = heap.top();
            for(int i = 0; i < top.second; i++)
                ret += top.first;
            heap.pop();
        }
        return ret;
    }
};