leetcode347. 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].

Note: 
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

假设有一个非空的整数数组,从中获得前k个出现频率最多的数字。

思路和代码

这里有一个额外要求即时间复杂度要优于O(n log n),也就是说我们无法采用先排序再顺序计算的方式来进行统计,因为最好的排序算法其平均的时间复杂度也需要O(n log n)。那么有没有别的方法可以让我们达到更好的效率呢?

这里的核心思路是桶排序,我们通过使用n+1个桶(其中第i个桶代表出现i次的数据)来汇拢每个数字出现的次数。先用HashMap来统计出现次数,然后将其丢到对应的桶中,最后从最高的桶开始向低的桶逐个遍历,取出前k个频率的数字。

    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer>[] buckets = new List[nums.length + 1];
        Map<Integer, Integer> frequency = new HashMap<Integer, Integer>();
        
        for(int num : nums){
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);
        }
        
        for(int key : frequency.keySet()){
            int frequencyOfKey = frequency.get(key);
            if(buckets[frequencyOfKey] == null){
                buckets[frequencyOfKey] = new ArrayList<Integer>();
            }
            buckets[frequencyOfKey].add(key);
        }
        
        List<Integer> result = new ArrayList<Integer>();
        for(int i = buckets.length-1 ; i>=0 && k>result.size() ; i--){
            if(buckets[i] != null){
                result.addAll(buckets[i]);
            }
        }
        return result;
    }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏来自地球男人的部落格

[LeetCode] 40. Combination Sum II

【原题】 Given a collection of candidate numbers (C) and a target number (T), fi...

1955
来自专栏java一日一条

Java 容器 & 泛型(2):ArrayList 、LinkedList和Vector比较

序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和...

911
来自专栏WD学习记录

牛客网 从上往下打印二叉树

711
来自专栏java一日一条

HashMap的实现原理

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒...

2592
来自专栏菩提树下的杨过

javascript:双链表-插入排序

数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入。 换成链表时,显然无需做这种大量移动,根据每个节点的...

22810
来自专栏云霄雨霁

字符串查找----R向单词查找树

1050
来自专栏java工会

java集合详解

23810
来自专栏码云1024

List Set Map比较

3424
来自专栏F_Alex

数据结构与算法(四)-线性表之循环链表

前言:前面几篇介绍了线性表的顺序和链式存储结构,其中链式存储结构为单向链表(即一个方向的有限长度、不循环的链表),对于单链表,由于每个节点只存储了向后的指针,到...

2123
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——IdentityHashMap

3759

扫码关注云+社区