看到这个题目首先想到是排序, 那么时间复杂度自然就是 O(NlgN). 那么使用二叉堆如何解决呢?
对于下面一个数组, 共有 12 个元素, 我们的目标就是找出第 5 大元素 --12
首先建立一个具有 M 个元素的最小堆, 那么堆顶是这 M 个元素的最小值, 接下来遍历剩下的元素, 如果一个元素小于堆顶元素则不做任何操作, 如果大于堆顶元素, 则替换该元素, 并且调整最小堆. 显然最后堆的 M 个元素是最大的 M 个元素, 而它们中最小的正式堆顶元素.
实现代码
- Heap <Integer> h = new Heap<>();
- Integer [] i = {7,5,15,3,17,2,20,24,1,9,12,8};
- int M = 5;
- for (int j = 0; j <M; j++)
- h.insert(i[j]);
- for (int j = M; j< i.length;j++)
- {
- if(i[j]> h.getFirst())
- {
- h.deleteFirst();
- h.insert(i[j]);
- }
- }
- System.out.println(h.getFirst());
Public void deleteFirst() 和 public Y getFirst() 方法分别获取堆顶数据和删除堆顶数据.
- public void deleteFirst()
- {
- delete(getFirst());
- }
- public Y getFirst()
- {
- return data.get(0);
- }
其余代码可在博文二叉堆的介绍和 Java 实现查看.
建立堆时间复杂度为 O(M), 遍历剩余数组的时间复杂度是 O(N-M), 每次调整堆的时间复杂度是 O(logM). 其中 2 和 3 是嵌套关系, 1 和 2,3 是并列关系, 所以总的最坏时间复杂度是 O((N-M)logM+M) . 当 M 远小于 N 的情况下, 也可以近似地认为是 O(NlogM). 值得一提的是, 这并不是求解该题时间复杂度最优的方法, 一种基于快速排序的方法可以将时间复杂度减低到线性, 这个等我们讲到快排时有机会再来看.
来源: http://www.bubuko.com/infodetail-3280468.html