面试常考算法题之 Top K 问题
大家好,这里是《齐姐聊算法》系列之 Top K 问题。
Top K 问题是面试中非常常考的算法题。
Leetcode 上这两题大同小异,这里以第一题为例。
题意:
给一组词,统计出现频率最高的 k 个。
比如说 “I love leetcode, I love coding” 中频率最高的 2 个就是 I 和 love 了。
有同学觉得这题特别简单,但其实这题只是母题,它可以升级到系统设计层面来问:
在某电商网站上,过去的一小时内卖出的最多的 k 种货物。
我们先看算法层面:
思路:
统计下所有词的频率,然后按频率排序取最高的前 k 个呗。
细节:
用 HashMap 存放单词的频率,用 minHeap/maxHeap 来取前 k 个。
实现:
建一个
HashMap <key = 单词,value = 出现频率>
,遍历整个数组,相应的把这个单词的出现次数 + 1.
这一步时间复杂度是 O(n).
用 size = k 的 minHeap 来存放结果,定义好题目中规定的比较顺序
a. 首先按照出现的频率排序;
b. 频率相同时,按字母顺序。
遍历这个 map,如果
a. minHeap 里面的单词数还不到 k 个的时候就加进去;
b. 或者遇到更高频的单词就把它替换掉。
时空复杂度分析:
第一步是 O(n),第三步是 nlog(k),所以加在一起时间复杂度是 O(nlogk).
用了一个额外的 heap 和 map,空间复杂度是 O(n).
代码:
如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!
我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!
更多干货文章见我的 Github: https://github.com/xiaoqi6666/NYCSDE
版权声明: 本文为 InfoQ 作者【码农田小齐】的原创文章。
原文链接:【http://xie.infoq.cn/article/34bafa25feb651f9bf05e86f0】。文章转载请联系作者。
评论 (2 条评论)