作者：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 個元素的算法稱為快速選擇算法。
時間複雜度 O(N)、空間複雜度 O(1)
只有當允許修改數組元素時才可以使用
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使用 HashMap 進行頻率統計，然後使用快速選擇或者堆的方式找出頻率 TopK。在海量數據場景下，也是先進行拆分再整合的方式來解決空間問題。
Count-Min Sketch維護 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
}
}
TrieTrie 樹又叫又叫字典樹、前綴樹、單詞查找樹，它是一顆多叉查找樹。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。
Trie 樹可以用於解決詞頻統計問題，只要在詞彙對應節點保存出現的頻率。它很好地適應海量數據場景，因為 Trie 樹通常不高，需要的空間不會很大。
參考資料今日問題
關鍵字inline的作用是什麼？
打卡格式：打卡第n天，答：...