【L347】Top-K问题

【L347】Top-K问题 描述

【Leet code 347】给定一个数组，返回前K个出现次数最多的元素。

思路

1.构建哈希表(std::unordered_map)记录元素和出现次数
2.构建优先队列(std::priority_queue)遍历哈希表入队
3.优先队列出队k个元素

【注意】优先队列的cmp函数和快排形式相反，想要得到大顶堆，left 复杂度

时间：O(N*log(k))
空间：O(N)

代码（C++）

class cmp_prt_queue
{
public:
    bool operator()(std::pair& v1, std::pair& v2)
    {
        if (v1.second < v2.second) return true;
        return false;
    }
};

class Solution {
public:
    std::vector topKFrequent(std::vector& src, int k)
    {
        std::vector topk;
        // 建立一个哈希表记录元素出现次数
        std::unordered_map temp_map;
        for (auto& ele : src)
        {
            if (temp_map.find(ele) == temp_map.end())
            {
                temp_map[ele] = 1;
            }
            else
            {
                temp_map[ele] ++;
            }
        }

        // 优先队列(, vector, cmp)
        std::priority_queue, std::vector>, cmp_prt_queue> prt_queue;
        for (auto iter : temp_map)
        {
            //std::cout << iter.first << "," << iter.second << std::endl;
            prt_queue.push(std::make_pair(iter.first, iter.second));
        }

        for (int idx = 0; idx < k; idx++)
        {
            topk.push_back(prt_queue.top().first);
            prt_queue.pop();
        }
        return topk;
    }
};