欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Top K问题

程序员文章站 2024-03-15 21:52:00
...
  1. 出现频率Top k的元素

    LeetCode 347

    给定一个非空整数数组,返回出现最多的k个元素

    输入:[1,1,1,2,2,3] k=2

    输出:[1,2]

    /*
    思路:对于此类求top k的问题,都可以用堆排序来实现。map容器和set容器是按照key值来进行排序的,且是按照从小到大排序。而priority_queue是优先级队列,它的底层是大顶堆。因此可以将元素的出现次数放在pair的key,元素的值放在pair的value,中间使用map来进行过度。
    */
    class Solution {
    public:
       vector<int> topKFrequent(vector<int>& nums, int k) {
           map<int, int> temp;
           priority_queue<pair<int, int>> heap;
           vector<int> res;
    
           for(int i = 0; i < nums.size(); ++i)
               temp[nums[i]]++;
           map<int, int>::iterator it = temp.begin();
    
           while(it != temp.end())
           {
               heap.push(make_pair(it->second, it->first));
               it++;
           }
    
           for(int i = 0; i < k; ++i)
           {
               res.push_back(heap.top().second);
               heap.pop();
           }
    
           return res;
       }
    };
  2. 出现频率Top k的单词

    LeetCode 692

    对于出现频率top k的单词,当几个单词出现频率一样时,按照字典顺序排列。而优先级队列底层大顶堆,不会按照字典顺序排列,需要我们对其比较函数进行重新定义。

    //第一个参数为元素类型,第二从参数是来承载底层数据结构堆的容器,第三个参数是一个比较类 
    priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> heap;
    
    //cmp的实现
    struct cmp
    {
       bool operator()(pair<string, int> a, pair<string, int> b)
       {
           if(a.second == b.second)
               return a.first > b.first;
           else
               return a.second < b.second;
       }
    };

    对于priority_queue来说,默认是大顶堆,也可以通过修改第三个参数,来将其改为小顶堆

    priority_queue<pair<string, int>, vector<pair<string, int>>, greater<pair<string,int>> > q; //小顶堆
    priority_queue<pair<string, int>, vector<pair<string, int>>, less<pair<string,int>> > q;  //大顶堆

    输入:[“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2

    输出:[“i”, “love”]

    /*
    思路:先将字符串和其对应的出现次数存在map中,然后将其存在priority_queue中,并重新定义其比较函数。最终取前k个即可。
    */
    struct cmp
    {
       bool operator()(pair<string, int> a, pair<string, int> b)
       {
           if(a.second == b.second)
               return a.first > b.first;
           else
               return a.second < b.second;
       }
    };
    
    class Solution {
    public:
       vector<string> topKFrequent(vector<string>& words, int k) {
           map<string, int> temp;
           priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> heap;
           vector<string> res;
    
           for(int i = 0; i < words.size(); ++i)
               temp[words[i]]++;
    
           map<string, int>::iterator it = temp.begin();
    
           while(it != temp.end())
           {
               heap.push(make_pair(it->first, it->second));
               it++;
           }
    
           for(int i = 0; i < k; ++i)
           {
               res.push_back(heap.top().first);
               heap.pop();
           }
           return res;
       }
    };