共计 450 个字符，预计需要花费 2 分钟才能阅读完成。
问题：
-
找第 K 大的数
- 在一个数组里
- 在数据流中
-
找最大的 K 个数
- 在一个数组里
- 在数据流中
-
找呈现频率最高的 K 个数
- 在一个数组中
- 在数据流中
- 在文件中
这种题适宜各种 follow up
核实问题：
是否须要准确的后果？
数据是离线的 (文件模式计算一次失去一个后果) 还是在线的(数据流可有限次查问实时后果)？
-
- –
问题 1 – 找第 K 大的数：
- 在一个整数数组中，找第 K 大的数 [Leetcode 题目]
解法 1: 快排整个数组 O(nlogn)
解法 2: 快选第 K 大 O(n) + 快排前 k 项 O(klogk) = O(n + klogk)
- 在一个数据流中，找第 K 大的数 [Leetcode 题目]
解法: 最小堆，最小堆的堆顶就是第 K 大的数，插入 O(lgk), 查问 O(1)
-
- –
问题 2 – 找最大的 K 个数：
- 在一个整数数组中，找最大的 K 个数
解法：同问题 1.1 解答
- 在一个数据流中，找最大 K 个数
解法: 同问题 1.2 解答，插入 O(lgk), 如果查问不须要放弃程序，则 O(n)，能够用 java 的 iterator 实现；如果查问须要放弃程序，则先无序的拿出，而后排序，即 O(klgk)
问题 3 – 找最高频的 K 个数
正文完