[LeetCode] 347. Top K Frequent Elements

【原题】 Given a non-empty array of integers, return the k most frequent elements.

For example, Given [1,1,1,2,2,3] and k = 2, return [1,2]. 【解释】 返回数组中出现最频繁的k个元素。 【思路】 思路一、hashmap统计频次,再对hashmap的value进行排序,取前面的k个最频繁的数。思路很简单,hashmap的value进行排序的过程,参照这里

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> hash=new HashMap<>();
         List<Integer> list=new ArrayList<Integer>();
            for(int i=0;i<nums.length;i++){
            //可以使用hash.put(nums[i], hash.containsKey(nums[i])? hash.get(nums[i]) + 1 : 1);语句代替
                if(hash.containsKey(nums[i]))
                    hash.put(nums[i], hash.get(nums[i])+1);
                else hash.put(nums[i],1);
            }
            Comparator<Map.Entry<Integer, Integer>> byMapValues = new Comparator<Map.Entry<Integer, Integer>>() {
                @Override
                public int compare(Map.Entry<Integer, Integer> left, Map.Entry<Integer, Integer> right) {
                       return right.getValue().compareTo(left.getValue());//按照单词频率逆序排列
                }
            };
            List<Map.Entry<Integer, Integer>> sortedListMap = new ArrayList<Map.Entry<Integer, Integer>>(hash.entrySet());
            Collections.sort(sortedListMap, byMapValues);
            for(int i=0;i<k;i++)
                list.add(sortedListMap.get(i).getKey());
            return list;
    }
}

思路二、使用堆 java中PriorityQueue就是使用堆的思想来维护一个优先级。 没什么好说的,看这里吧。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java爬坑系列

【Java入门提高篇】Day19 Java集合类详解(二)Map接口

  上一篇里介绍了集合家族里的大族长——Collection接口,今天来看看集合家族里的二族长——Map接口。

922
来自专栏haifeiWu与他朋友们的专栏

聊聊HashSet源码

今天聊一下HashSet源码,HashSet内部基本使用HashMap来实现,本博客将通过一下几个方向讲解。

753
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

983
来自专栏苍云横渡学习笔记

【JavaSE(十一)】Java集合框架(下)

2164
来自专栏desperate633

LintCode 简化路径题目分析代码

思路比较简单,遇到..就回到上一级,遇到.或者空就不处理。 我们使用一个队列来处理,同时将三个需要特殊处理的字符存到一个set里面

561
来自专栏Danny的专栏

Java基础——Set接口

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

932
来自专栏Java帮帮-微信公众号-技术文章全总结

第十九天 集合-Map接口容器工具类集合框架总结【悟空教程】

Map集合的特点,如是否可重复,是否有序仅作用在键上,如HashMap集合的键不得重复,值可以重复。

1213
来自专栏用户画像

HashSet和HashMap的区别 && HashTable和HashMap的区别

2.Hashtable 中的方法是同步的,而HashMap中的方法在缺省情况下是非同步的。

743
来自专栏绿巨人专栏

Java: Replace a string from multiple replaced strings to multiple substitutes

3338
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-18(01)总结Map,HashMap,HashMap与Hashtable区别,Collections工具类

1:Map(掌握) (1)将键映射到值的对象。一个映射不能包含重复的键;每个键最多只能映射到一个值。 (2)Map和Collection的区别? A:M...

2254

扫码关注云+社区