k个最大的数及变种小结
声明
文章均为本人技术笔记，转载请注明出处：
[1] https://segmentfault.com/u/yzwall [2] blog.csdn.net/j_dark/0 堆实现
堆逻辑上是完全二叉树，物理上表现为数组，节点编号默认从0开始；
构造函数public Heap(boolean flag)，flag为真建立最小堆，否则建立最大堆；向外提供接口如下： offer(int x)：将元素x加入堆中；poll()：弹出堆顶，空堆弹出Integer.MAX_VALUE；top()：返回堆顶值但不弹出，空堆返回Integer.MAX_VALUE，size()：返回堆中元素总数；
/** * 堆实现 * @author yzwall */public class Heap { private ArrayList array; // true代表最小堆, false代表最大堆 private boolean flag; public Heap(boolean flag) { this.array = new ArrayList (); this.flag = flag; } // 检查父节点a与其孩子节点b是否满足堆序 private boolean isOrder(int a, int b) { if (flag) { return a < b ? true : false; } return a > b ? true : false; } /** * 添加元素，时间复杂度O(logn) * 1. 将新元素添加到完全二叉树尾部，物理上为数组尾部 * 2. 新元素向上检查是否满足堆序 */ public void offer(int newNum) { array.add(newNum); int index = array.size() - 1; shiftUp(index); } // 上滤操作，检查index与父节点是否满足堆序 private void shiftUp(int index) { while (index != 0) { int parent = (index - 1) / 2; if (isOrder(array.get(parent), array.get(index))) { break; } // 不满足堆序，互换位置 int temp = array.get(index); array.set(index, array.get(parent)); array.set(parent, temp); index = parent; } } /** * 删除堆顶，时间复杂度O(logn) * 1. 将末元素覆盖堆顶（删除堆顶） * 2. 删除末元素原来位置（保证堆节点总数-1） * 3. 向下检查新堆顶与孩子节点的堆序性 */ public int poll() { int top = top(); if (top == Integer.MAX_VALUE) { return top; } array.set(0, array.get(array.size() - 1)); array.remove(array.size() - 1); shiftDown(0); return top; } // 下滤操作，检查index与孩子节点是否满足堆序 private void shiftDown(int index) { int bigIndex, leftIndex, rightIndex; boolean hasLChild = false, hasRChild = false; while (true) { leftIndex = 2 * index + 1; rightIndex = 2 * index + 2; if (leftIndex < array.size() && array.get(leftIndex) != Integer.MAX_VALUE) { hasLChild = true; } if (rightIndex < array.size() && array.get(rightIndex) != Integer.MAX_VALUE) { hasRChild = true; } // 叶子节点默认满足堆序 if (!hasLChild && !hasRChild) { break; } else if(hasLChild && hasRChild) { bigIndex = isOrder(array.get(leftIndex), array.get(rightIndex)) ? leftIndex : rightIndex; } else if(hasLChild) { bigIndex = leftIndex; } else { bigIndex = rightIndex; } if (isOrder(array.get(index), array.get(bigIndex))) { break; } // 不满足堆序，index与较大孩子节点互换位置 int temp = array.get(index); array.set(index, array.get(bigIndex)); array.set(bigIndex, temp); index = bigIndex; hasLChild = false; hasRChild = false; } } // 获取堆顶 public int top() { return array.size() == 0 ? Integer.MAX_VALUE : array.get(0); } // 返回堆大小 public int size() { return array.size(); }} 1 求k个最大的数
lintcode 544 Top K Largest Numbers(解法1~解法3，解法4无法保证结果有序)
1.1 解法1 最大堆实现$O(nlog n)$时间复杂度
将所有元素加入最大堆中（当元素总数n特别大时，创建堆时间开销大，花费$O(nlog n)$）；
弹出堆顶k次，保证结果降序（花费时间$O(nlog k)$）；
/** * 求给定数组前k大数，结果要求以降序给出 * http://www.lintcode.com/zh-cn/problem/top-k-largest-numbers/ * 解法2：最大堆解决前k大数：将所有元素入堆，最后弹出k次，时间复杂度O(nlogn)，大数据量时速度低于最小堆解法 * @author yzwall */class Solution11 { public int[] topk(int[] nums, int k) { Heap heap = new Heap(false); for (int i = 0; i < nums.length; i++) { heap.offer(nums[i]); } int[] topK = new int[k]; for (int i = 0; i < k; i++) { topK[i] = heap.poll(); } return topK; }} 1.2 解法2 最小堆实现$O(nlog n)$时间复杂度
针对最大堆解法创建堆开销时间过高，维护一个元素总数最多为k的最小堆；每次淘汰待进堆元素和堆顶的较小者，保证堆中元素始终为已扫描数据中的最大的k个数；
解法：建立最小堆（花费时间$O(nlog k)$）；
弹出堆顶k次（花费时间$O(klog k)$）；
根据题意将结果逆序（花费时间$O(k)$）；；
/** * 求给定数组前k大数，结果要求以降序给出 * http://www.lintcode.com/zh-cn/problem/top-k-largest-numbers/ * 解法2：最小堆解决前k大数，时间复杂度O(nlogn) * @author yzwall */class Solution10 { public int[] topk(int[] nums, int k) { Heap heap = new Heap(true); for (int i = 0; i < nums.length; i++) { if (heap.size() < k) { heap.offer(nums[i]); } else { // 更新前k大数中最小值 if (heap.top() < nums[i]) { heap.poll(); heap.offer(nums[i]); } } } int[] topK = new int[k]; for (int i = 0; i < k; i++) { topK[i] = heap.poll(); } for (int i = 0, j = k - 1; i < j; i++, j--) { int temp = topK[i]; topK[i] = topK[j]; topK[j] = temp; } return topK; }} 1.3 解法3 优先队列实现$O(nlog n)$时间复杂度
优先队列可用来实现最大堆（解法1）和最小堆（解法2），根据需要重写构造方法中的比较器；
给出优先队列实现最大堆解法：/** * 求给定数组前k大数，要求给出降序结果 * http://www.lintcode.com/zh-cn/problem/top-k-largest-numbers/ * 解法3：重写优先队列比较器实现最大堆 * @author yzwall */class Solution { public int[] topk(int[] nums, int k) { int[] topK = new int[k]; PriorityQueue pq = new PriorityQueue<>(k, new Comparator () { public int compare(Integer o1, Integer o2) { return o1 > o2 ? -1 : 1; } }); for (int i = 0; i < nums.length; i++) { pq.offer(nums[i]); } for (int i = 0; i < k; i++) { topK[i] = pq.poll(); } return topK; }} 1.4 解法4 Partiton $O(n)$时间复杂度
将“求k个最大数”转变为：
Partition切分思想求出数组第k小数；
切分操作完成后，此时数组前k个数必然是最大的k个数
注意：切分操作完成后，结果乱序；
解法对比
| --- | 是否修改输入 | 时间复杂度 | 空间复杂度 | 是否按序输出结果 |
|---|---|---|---|---|
| 解法1 | 否 | $O(nlog n)$ | $O(n)$ | 是 |
| 解法2 | 否 | $O(nlog k)$ | $O(n)$ | 是 |
| 解法3 | 否 | $O(nlog n)$或者$O(nlog k)$ | $O(n)$ | 是 |
| 解法4 | 是 | $O(n)$ | $O(1)$ | 否 |
解法1：最大堆时间复杂度最高，空间复杂度最高；
解法2：最小堆在解法1基础上在创建堆时控制入堆元素数量，降低创建堆时间开销；
解法3：优先队列是堆的库函数实现，只需要根据题意重写比较器
java.util.Comparator<T>，无需手写堆；解法4：时间复杂度和空间复杂度均最低，但是Partition切分算法无法保证最终结果有序；
2 求出现次数最多的k个单词
lintcode 471 Top K Frequent Words
使用优先队列实现，根据题意：
你需要按照单词的词频排序后输出，越高频的词排在越前面。如果两个单词出现的次数相同，则词典序小的排在前面。
解法如下：
使用
HashMap统计单词出现次数；优先队列队首维护出现次数最多单词；
优先队列出队k次；
创建优先队列时候需重写比较器，单词字典序比较使用java.util.String类自带的compareTo方法（String类实现Comparable<T>接口）；
/** * 优先队列实现，字典序比较使用String类自带CompareTo方法 * 求出现次数最多的K个单词，要求结果按序输出（出现次数升序输出，相同按照单词字典序升序输出）； * http://www.lintcode.com/en/problem/top-k-frequent-words/ * @author yzwall */class Solution { private class Word { String word; int count; public Word(String word, int count) { this.word = word; this.count = count; } } public String[] topKFrequentWords(String[] words, int k) { PriorityQueue pq = new PriorityQueue<>(words.length, new Comparator () { public int compare(Word o1, Word o2) { if (o1.count != o2.count) { return o1.count > o2.count ? -1 : 1; } else { return o1.word.compareTo(o2.word); } } }); HashMap map = new HashMap<>(); for (String word : words) { if (map.containsKey(word)) { map.put(word, map.get(word) + 1); } else { map.put(word, 0); } } for (Map.Entry entry : map.entrySet()) { pq.offer(new Word(entry.getKey(), entry.getValue())); } String[] topK = new String[k]; for (int i = 0; i < k; i++) { if (!pq.isEmpty()){ topK[i] = pq.poll().word; } else { break; } } return topK; }} 3 求距离最近的k个点
lintcode 612 K Closest Points
求距离origit点最近的k个点，结果要求以距离升序输出，距离相同按x坐标升序，x坐标相同按照y坐标升序
解法：根据题意使用优先队列java.util.PriorityQueue<T>，按照题意构造比较器Compator<T>; /** * 求距离origit点最近的k个点，距离相同按x坐标升序，x坐标相同按照y坐标升序 * http://www.lintcode.com/en/problem/k-closest-points/ * 使用优先队列java.util.PriorityQueue，按照题意构造比较器Compator; * @author yzwall */class Solution { private class Point { int x, y; Point() { x = 0; y = 0; }; Point(int a, int b) { x = a; y = b; } } private class PPoint { int x, y, dist; PPoint(Point p, int dist) { this.x = p.x; this.y = p.y; this.dist = dist; } } private int distance(Point src, Point dest) { int xx = src.x - dest.x; int yy = src.y - dest.y; return xx * xx + yy * yy; } public Point[] kClosest(Point[] points, Point origin, int k) { // 使用new PriorityQueue<>(new Comparatpr ()) lintcode编译会报错 PriorityQueue pq = new PriorityQueue<>(k, new Comparator (){ @Override public int compare(PPoint o1, PPoint o2) { if (o1.dist != o2.dist) { return o1.dist - o2.dist; } else { if (o1.x != o2.x) { return o1.x - o2.x; } return o1.y - o2.y; } } }); if (points == null || points.length < k) { return null; } Point[] array = new Point[k]; for (Point point : points) { pq.offer(new PPoint(point, distance(origin, point))); } for (int i = 0; i < k; i++) { PPoint temp = pq.poll(); array[i] = new Point(temp.x, temp.y); } return array; }}