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
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
网站与APP抓包分析(应用)通过Python实现APP内容爬虫
1、APP数据交互分析 以某考试练习APP为例(只爬取题目,无答案) 1.1、环境准备 (1)PC(笔记本)上安装WIFI外放工具,例如360免费WIFI(2)手机安装APP后,注册账号并登陆 1.2、请求分析 运行APP,并触发所需场景,定位请求记录请求分析通过以上过程可知,习题加载过程为:HOST: 182.92.213.77:9011请求类型:POSTURL: http://182.92.213.77:9011/safeEden/r/p/d/ugetquest.dCookie:Uid=155710&Slid=1其中Uid=用户ID,Slid=习题归属分组,每组加载3道题。 2、Python脚本实现 构造习题加载URL,通过Python 构造HTTP POST清洗;通过循环执行习题获取请求,遍历获取习题,并写入txt文档;对文档进行去重,可得APP中大部分习题。 2.1、Python脚本 #!/usr/bin/env python #-*-coding:gb2312-*- from urllib.request import urlopen def readquest(v)...
- 下一篇
机器学习该怎么入门?
我们从下面3步详细看下如何去学习 第1步:基础知识学习机器学习需要具备数学和编程基础。1)数学理论:微积分、线性代数、统计学 可汗学院,是由孟加拉裔美国人萨尔曼·可汗创立的一家教育性非营利组织,主旨在于利用网络影片进行免费授课。可汗学院公开课:微积分-积分学可汗学院公开课:微积分-微分学 《沉浸式线性代数》(Immersive Linear Algebra) :通过可以活动的图像,你可以观察和理解难懂的数学理论:http://immersivemath.com/ila/index.html 可汗学院公开课:线性代数麻省理工公开课:线性代数 可汗学院公开课:统计学可汗学院公开课:概率 这个是我讲的统计学,内部案例用Python实现,结合生活中的案例可以通俗易懂的学会:从零学会人工智能基础知识:统计概率 3Blue1Brown制作的数学科普视频,通过动画的方式将数学讲的通俗易懂。官网地址:https://space.bilibili.com/88461692 2)编程能力:Python这部门内容在之前的文章中有聊过如何学习:做数据分析不得不看的书有哪些?www.zhihu.com图标 第...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Hadoop3单机部署,实现最简伪集群
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Docker使用Oracle官方镜像安装(12C,18C,19C)