347.前k个高频元素——最小堆的运用

太过爱你忘了你带给我的痛 2022-12-04 08:56 67阅读 0赞

### 文章目录 ###

*  前k个高频元素
 *  最小堆
 *  代码与思路
 *   *  java代码
     *  c++代码

# 前k个高频元素 #

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = \[1,1,1,2,2,3\], k = 2  
输出: \[1,2\]  
示例 2:

输入: nums = \[1\], k = 1  
输出: \[1\]

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。  
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。  
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。  
你可以按任意顺序返回答案。

# 最小堆 #

最小堆，是一种经过排序的完全二叉树，，非叶子结点的值不大于左孩子和右孩子的值。  
![在这里插入图片描述][20200907145130628.png_pic_center]

# 代码与思路 #

## java代码 ##

class Solution { 
        public int[] topKFrequent(int[] nums, int k) { 
        	 //1. 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
        	Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        	for(int num:nums) { 
        		map.put(num, map.getOrDefault(num,0)+1);
        	}
        	// 2.遍历map，用最小堆保存频率最大的k个元素
        	// 2.1 PriorityQueue初始化
        	PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() { 
    
    			@Override
    			public int compare(Integer a, Integer b) { 
    				return map.get(a)-map.get(b);
    			}
        		
    		});
        	//2.2 开始添加元素到最小堆
        	for(Integer key:map.keySet()){ 
        		if(pq.size()<k) { //堆中的元素小于k时，加入
        			pq.add(key);
        		}else if(map.get(key)>map.get(pq.peek())) { 
        			//堆中的元素等于k时，就判断
        			pq.remove();
        			pq.add(key);
        		}
        	}
        	//3. 取出最小堆中的元素
            int[] ret = new int[k];
            for (int i = 0; i < k; ++i) { 
                ret[i] =pq.remove();
            }
        	return ret;
        }
    }

## c++代码 ##

class Solution { 
    public:
        static bool cmp(pair<int, int>& m, pair<int, int>& n) { 
            return m.second > n.second;
        }
    
        vector<int> topKFrequent(vector<int>& nums, int k) { 
            unordered_map<int, int> occurrences;
            for (auto& v : nums) { 
                occurrences[v]++;
            }
    
            // pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
            priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
            for (auto& [num, count] : occurrences) { 
                if (q.size() == k) { 
                    if (q.top().second < count) { 
                        q.pop();
                        q.emplace(num, count);
                    }
                } else { 
                    q.emplace(num, count);
                }
            }
            vector<int> ret;
            while (!q.empty()) { 
                ret.emplace_back(q.top().first);
                q.pop();
            }
            return ret;
        }
    };

[20200907145130628.png_pic_center]: /images/20221123/6fc0d2f63eb741f99179567c0434cd65.png