网站seo好学吗,虚拟主机和vps的区别,外贸网站模板建立,网页版微信app给定一个非空的整数数组#xff0c;返回其中出现频率前 k 高的元素。
示例 1:
输入: nums [1,1,1,2,2,3], k 2
输出: [1,2]
示例 2:输入: nums [1], k 1
输出: [1]提示#xff1a;
你可以假设给定的 k 总是合理的#xff0c;且 1 ≤ 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 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。// 时间复杂度O(nlogk)
// 空间复杂度O(n)
class Solution {
public:// 小顶堆class myCompare {public:bool operator()(const pairint, int lhs, const pairint, int rhs) {return lhs.second rhs.second;}};vectorint topKFrequent(vectorint nums, int k) {mapint, int m;for (const auto x: nums) {m[x];}priority_queuepairint, int, vectorpairint, int, myCompare my_pri;auto iter m.begin();for (int i0; ik; i) {my_pri.push(*iter);iter;}for (; iter ! m.end(); iter) {my_pri.push(*iter);my_pri.pop();}vectorint res;while(my_pri.size() 0) {res.push_back(my_pri.top().first);my_pri.pop();}return res;}
};
