作者:CyC2018 链接:https://www.nowcoder.com/discuss/150681
找出一组数最大的 K 个数。
Leetcode : 215. Kth Largest Element in an Array
https://leetcode.com/problems/kth-largest-element-in-an-array/description/
快速排序的 partition() 方法,会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j],且 a[j+1..h] 大于等于 a[j],此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 K 个元素,这种找第 K 个元素的算法称为快速选择算法。
public int findKthElement(int[] nums, int k) { k = nums.length - k; int l = 0, h = nums.length - 1; while (l < h) { int j = partition(nums, l, h); if (j == k) { break; } else if (j < k) { l = j + 1; } else { h = j - 1; } } return nums[k];}
private int partition(int[] a, int l, int h) { int i = l, j = h + 1; while (true) { while (a[++i] < a[l] && i < h) ; while (a[--j] > a[l] && j > l) ; if (i >= j) { break; } swap(a, i, j); } swap(a, l, j); return j;}
private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t;}
维护一个大小为 K 的最大堆,那么在堆中的数都是 TopK。
使用小顶堆来维护最大堆,而不能直接创建一个大顶堆并设置一个大小,企图让大顶堆中的元素都是最大元素。
维护一个大小为 K 的最大堆过程如下:在添加一个元素之后,如果小顶堆的大小大于 K,那么需要将小顶堆的堆顶元素去除。
public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆 for (int val : nums) { pq.add(val); if (pq.size() > k) // 维护堆的大小为 K pq.poll(); } return pq.peek();}
在这种场景下,单机通常不能存放下所有数据。
Heavy Hitters 问题要求找出一个数据流的最频繁出现的 K 个数,比如热门搜索词汇等。
使用 HashMap 进行频率统计,然后使用快速选择或者堆的方式找出频率 TopK。在海量数据场景下,也是先进行拆分再整合的方式来解决空间问题。
维护 d*w 大小的二维统计数组,其中 d 是哈希函数的个数,w 根据情况而定。
该算法的思想和布隆过滤器类似,具有一定的误差,特别是当 w 很小时。但是它能够在单机环境下解决海量数据的频率统计问题。
public class CountMinSketch {
private int d; private int w;
private long estimators[][];
public CountMinSketch(int d, int w) { this.d = d; this.w = w; }
public void add(int value) { for (int i = 0; i < d; i++) estimators[i][hash(value, i)]++; }
public long estimateFrequency(int value) { long minimum = Integer.MAX_VALUE; for (int i = 0; i < d; i++) { minimum = Math.min(minimum, estimators[i][hash(value, i)]); } return minimum; }
private int hash(int value, int i) { return 0; // use ith hash function }}
Trie 树又叫又叫字典树、前缀树、单词查找树,它是一颗多叉查找树。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。
Trie 树可以用于解决词频统计问题,只要在词汇对应节点保存出现的频率。它很好地适应海量数据场景,因为 Trie 树通常不高,需要的空间不会很大。
END
觉得文章不错的,欢迎点好看和转发,长按下图关注程序员乔戈里,收看更多精彩。