前K个高频元素

时间:2022-12-31 04:24:30

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

示例 1:

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

示例 2:

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

说明:

  • 你可以假设给定的 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
  • 你的算法的时间复杂度必须优于 O(n log n) , 是数组的大小。
import java.util.*;

class Solution {
static class MaxHeapComparator implements Comparator<Map.Entry<Integer,Integer>>{ @Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
return o2.getValue()-o1.getValue();
}
} public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i])){
int times = map.get(nums[i]).intValue()+1;
map.put(nums[i],times);
}else {
map.put(nums[i],1);
}
} List< Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet()); PriorityQueue< Map.Entry<Integer,Integer>> queue= new PriorityQueue<>(new MaxHeapComparator());
for (int i = 0; i < list.size(); i++) {
queue.add(list.get(i));
} List<Integer> resList = new ArrayList<>();
for (int i = 0; i < k; i++) {
resList.add(queue.poll().getKey());
} return resList;
}
}

  

前K个高频元素的更多相关文章

  1. 【LeetCode题解】347&lowbar;前K个高频元素(Top-K-Frequent-Elements)

    目录 描述 解法一:排序算法(不满足时间复杂度要求) Java 实现 Python 实现 复杂度分析 解法二:最小堆 思路 Java 实现 Python 实现 复杂度分析 解法三:桶排序(bucket ...

  2. Top K Frequent Elements 前K个高频元素

    Top K Frequent Elements 347. Top K Frequent Elements [LeetCode] Top K Frequent Elements 前K个高频元素

  3. LeetCode:前K个高频元素【347】

    LeetCode:前K个高频元素[347] 题目描述 给定一个非空的整数数组,返回其中出现频率前 k 高的元素. 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [ ...

  4. 代码题(3)— 最小的k个数、数组中的第K个最大元素、前K个高频元素

    1.题目:输入n个整数,找出其中最小的K个数. 例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4. 快排思路(掌握): class Solution { public ...

  5. leetcode347&period; 前 K 个高频元素

    题目最终需要返回的是前 kk 个频率最大的元素,可以想到借助堆这种数据结构,对于 kk 频率之后的元素不用再去处理,进一步优化时间复杂度. 具体操作为: 借助 哈希表 来建立数字和其出现次数的映射,遍 ...

  6. Java实现 LeetCode 347 前 K 个高频元素

    347. 前 K 个高频元素 给定一个非空的整数数组,返回其中出现频率前 k 高的元素. 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输 ...

  7. 力扣 - 347&period; 前 K 个高频元素

    目录 题目 思路1(哈希表与排序) 代码 复杂度分析 思路2(建堆) 代码 复杂度分析 题目 347. 前 K 个高频元素 思路1(哈希表与排序) 先用哈希表记录所有的值出现的次数 然后将按照出现的次 ...

  8. &lbrack;LeetCode&rsqb; Top K Frequent Elements 前K个高频元素

    Given a non-empty array of integers, return the k most frequent elements. For example,Given [1,1,1,2 ...

  9. &lbrack;Swift&rsqb;LeetCode347&period; 前K个高频元素 &vert; Top K Frequent Elements

    Given a non-empty array of integers, return the k most frequent elements. Example 1: Input: nums = [ ...

随机推荐

  1. cocos2d-x:Particle System(粒子系统)

    一.粒子系统简介: 粒子系统最早出现在80年代,主要用于解决由大量按一定规则运动(变化)的微小物质在计算机上的生成和显示问题.Particle System的应用非常广泛,大的可以模拟原子弹爆炸,星云 ...

  2. centos 搭建ftp服务器

    1.安装vsftpd sudo yum install vsftpd 2.配置vsftpd.conf # Allow anonymous FTP? (Beware - allowed by defau ...

  3. 在ASP&period;MVC中使用Ajax

    Asp.net MVC 抛弃了Asp.net WebForm那种高度封装的控件,让我们跟底层的HTML有了更多的亲近.可以更*.更灵活的去控制HTML的结构.样式和行为.Asp.net MVC可以更 ...

  4. myeclipse&plus;tomcat 工程名改名的问题 ——————完美解决方案

    当建好的工程再重命名之后,发布和访问的时候都还是原来的名字,这个问题纠结了我很久,最好找到解决方法,这里分享一下,希望大家不要再受这种困惑.解决方法: 点击工程右键->properties-&g ...

  5. PHP 中 Date 函数与实际时间相差8小时的解决方法

    PHP 中的 date() 函数显示的时间是格林威治时间,和北京时间正好相差8个小时,其他时间相关的函数,如 strtotime() 也有相同的问题,同样可以通过下面的方法来解决: 1. 修改php. ...

  6. iOS 之 界面编程解析

    参考:http://www.cocoachina.com/design/20151225/14789.html 0. 内容概述 基础与本质:说明普遍意义上的UI系统的三大模块,让读者从整体上对UI系统 ...

  7. 如何编写高效的SQL

    编写高效的sql可以给用户带来好的体验,需要开发这没有意识到这一点因为他们不关心也不知道怎么做.高效的sql可以给用户节省很多时间,这样就不需要dba来找上门,也不需要搭建RCA和性能调优. 性能不好 ...

  8. windows下python3&period;5使用pip离线安装whl包

    0. 绪论 Windows离线断网环境下安装Python包,配置环境,准备用来生成word模版.姑且记录一下 生产环境 : windows 7 windows10 python 3.5.2 pip 1 ...

  9. 一名全栈设计师的Mac工具箱(设计&comma;开发&comma;效率)

        我喜欢把自己定义为一个会一些设计的全栈工程师.在一些大型企业项目中,我一般担任架构师的角色,而到了我自己负责的个人或开源项目中,我就成了一名全栈设计师.我喜欢用自学而来的那些设计技能进行网站或 ...

  10. 深度学习笔记(八)Focal Loss

    论文:Focal Loss for Dense Object Detection 论文链接:https://arxiv.org/abs/1708.02002 一. 提出背景 object detect ...