LeetCode 347: 前 K 个高频元素 Top K Frequent Elements-阿里云开发者社区

开发者社区> 爱写Bug> 正文

LeetCode 347: 前 K 个高频元素 Top K Frequent Elements

简介:
+关注继续查看

题目:

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

Given a non-empty array of integers, return the K most frequent elements.

示例 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 是数组的大小。

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)

首先频率统计最优雅的方法应该是借助哈希映射, key 为元素, value 为频率. 其时间复杂度为 O(n)

重点是返回前 K 个频率最高的元素, 所以另一种更简单的方法是直接借助 堆(优先队列) 这种数据结构

维护一个 大小为 K 的堆来动态存储前 K 个频率最高的元素, 其时间复杂度为 O(n)

代码:

Java:

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        // 建立哈希映射
        HashMap<Integer, Integer> count = new HashMap();
        // 频率统计
        for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1);

        // 建立优先队列, 借助 Lambda 表达式
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>((a, b) -> count.get(a) - count.get(b));
        // 也可以借助 compare 比较函数
        // PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
        //     @Override
        //     public int compare(Integer a, Integer b) {
        //         return map.get(a) - map.get(b);
        //     }
        // });
        
        // 维护一个大小为 k 的已排序的优先队列
        for (int n : count.keySet()) {
            heap.add(n);
            if (heap.size() > k)
                heap.poll();
        }

        // 返回结果
        List<Integer> top_k = new LinkedList();
        while (!heap.isEmpty())
            top_k.add(heap.poll());
        return top_k;
    }
}

Python:

Python 基础库里的 heapq 堆数据结构, 有两个函数:

  • nlargest
  • nsmallest

例如

heapq.nsmallest(n, nums)

表示取迭代器 nums 前 n 个最大元素, 该函数还能接受一个 key 关键字,以应对复杂的数据结构

结合 collections.Counter() 频率统计函数, 两行代码即可解决

class Solution:
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """ 
        count = collections.Counter(nums)   
        return heapq.nlargest(k, count.keys(), key=count.get) 

注意体会关键字参数的作用: key=count.get

欢迎关注微.信公.众号: 爱写Bug
爱写Bug.jpeg

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9497 0
[翻译svg教程]svg中矩形元素 rect
svg 元素 是一个矩形元素,用这个元素,可以你可以绘制矩形,设置矩形宽高,边框的宽度颜色,矩形的填充颜色,是否用圆角等 rect 示例 这个矩形的                    位置:用x和y属性定义,需要注意的是这个位置是相对于 这个矩形的父节点定义的 ...
748 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13186 0
为什么阿里巴巴禁止在 foreach 循环里进行元素的 remove/add 操作
我们使用的增强for循环,其实是Java提供的语法糖,其实现原理是借助Iterator进行元素的遍历。
4832 0
jQuery操纵DOM元素属性 attr()和removeAtrr()方法使用详解
原文:jQuery操纵DOM元素属性 attr()和removeAtrr()方法使用详解 jQuery操纵DOM元素属性 attr()和removeAtrr()方法使用详解   jQuery中操纵元素属性的方法:   attr(): 读或者写匹配元素的属性值.
899 0
LeetCode 73 Set Matrix Zeroes(设矩阵元素为0)(Array)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52139263 翻译 给定一个mm x nn的矩阵matrix,如果其中一个元素为0,那么将其所在的行和列的元素统统设为0。
808 0
Tomcat集群配置元素Receiver属性(一)
Tomcat集群配置元素Receiver属性(一)      属性:className、含义:该Receiver实现要使用的完全限定的Java类名。对Tomcat 6.0。有可供使用的两个类:org.apache.catalina.tribes.transport.bio.BioReceiver和org.apache.catalina.tribes.transport.nio.NioReceiver    属性:address、含义:监听人向复制消息的IP地址或完全限定主机名的IP地址。
582 0
+关注
爱写Bug
欢迎关注公众号:爱写Bug
85
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载