【LeetCode 27】347.前k个高频元素

简介: 【LeetCode 27】347.前k个高频元素

一、题意

二、思考过程

这道题主要涉及下面三个部分:

  • 统计元素出现的次数
  • 对次数排序(用堆实现)
  • 找出前k个高频元素

Notes:

  • 我们要使用小顶堆统计最大的前k个元素

三、完整代码

class Solution {
public:
    //小顶堆
    class mycomparision{
        public:
            bool operator()(const pair<int,int>& lhs,const pair<int,int>& rhs)
            {
                return lhs.second >rhs.second;
            }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        //统计元素出现的次数
        unordered_map<int,int> map;
        for(int i=0;i<nums.size();i++)
        {
            map[nums[i]]++;
        }
        //对元素出现的次数进行排序
        //定义一个小顶堆,大小为k
        priority_queue<pair<int,int>,vector<pair <int,int>>,
        mycomparision>pri_que;
        //用固定大小为k的小顶堆遍历所有元素出现次数的整数值
        for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++)
        {
            pri_que.push(*it);
            if(pri_que.size()>k)//如果堆的大小大于k,则队列弹出,保证堆的大小一直为k
            {
                pri_que.pop();
            }
        }
        //找出前k个高频元素,因为小顶堆先弹出的是最小的元素,所以倒序输出列result
        //数组中
        vector<int> result (k);
        for(int i=k-1;i>=0;i--)
        {
            result[i]=pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};


目录
相关文章
|
2月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
36 1
|
2月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
30 0
|
2月前
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
32 0
|
4月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
4月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer II 082. 含有重复元素集合的组合
解决LeetCode平台《剑指 Offer II 082. 含有重复元素集合的组合》题目的Python代码实现,通过深度优先搜索算法找出所有和为特定目标值的数字组合,并在搜索过程中通过排序和跳过重复元素来避免解集中出现重复组合。
41 2
|
4月前
|
算法
LeetCode第27题移除元素
这篇文章介绍了LeetCode第27题"移除元素"的解题方法,通过使用双指针技巧,有效移除数组中特定值的元素并返回新数组的长度。
|
4月前
|
算法 索引 Python
【Leetcode刷题Python】34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)
解决LeetCode "在排序数组中查找元素的第一个和最后一个位置" 问题的方法。第一种方法是使用两次二分查找,首先找到目标值的最左边界,然后找到最右边界。第二种方法是利用Python的list.index()方法,先正序找到起始位置,再逆序找到结束位置,并给出了两种方法的Python实现代码。
62 0
|
4月前
|
Python
【Leetcode刷题Python】203.移除链表元素
文章提供了三种删除链表中特定值节点的方法:迭代法、虚拟节点迭代删除法和递归法,并给出了相应的Python实现代码。
26 0
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素