作者：vincent-duan，專注 Java，沉迷開源，架構師社區合夥人！
面試題目：如何在10億個整數中找出前1000個最大的數。
我們知道排序算法有很多：
- 冒泡算法：通過兩層for循環，外層第一次循環找到數組中最大的元素放置在倒數第一個位置，第二次循環找到第二大的元素放置在倒數第二個位置。。。循環N次就可以找到TopN。
- 缺點：冒泡排序內層循環需要大量交換元素。複雜度介於O(n)和O(n^2)之間。
- 快速排序：選一個基準元素，每次排序可以將這個基準元素擱置在正確的位置，左邊都是比基準小的元素，右邊都是比基準大的元素從而將數組分成左右兩部分，分而治之。TopN問題也同樣如此，選擇一個基準元素並通過快速排序將基準元素擱置在正確的位置，如果左邊的元素個數小於1000，那麼繼續從基準右邊排序，如果左邊元素個數大於1000，那麼從基準左邊排序，直到基準的位置正好在1000，結束。
- 缺點：第一次排序複雜度是O(n),第二次排序複雜度是O(n/2),第三次排序複雜度是O(n/4)....
- 文件存儲，分而治之:
- 將比基準小的元素存儲在txt1中，比基準大的文件存儲在txt2中，然後通過類似方法二的形式，最後求出TopN。
- 缺點：磁盤讀取，寫入次數過多。
- MapReduce:單機內存和性能確實受限，那麼我們可以將10億個分段存儲在不同的機器上，每臺機器計算各自的TopN，最後彙總。
- 缺點：空間換時間。
最優解：小頂堆
在內存中維護一個長度為N的數組，根據堆的性質，每一個節點都比他的左右子節點小，先取出前N個數並構建小頂堆，然後將所有數據與堆頂比較大小，如果比堆頂小就直接丟棄，如果比堆頂大則替換堆頂，並且重新構建這個堆。
構建小頂堆的過程：先要找到最後一個非葉子節點，數組的長度為6，那麼最後一個非葉子節點就是：長度/2-1，也就是6/2-1=2，然後下一步就是比較該節點值和它的左右節點值，如果該節點大於其左\\右子樹的值就交換（意思就是將最小的值放到該節點）。如果該節點不是葉子結點，則遞歸這一過程，直到這個節點變成葉子節點。
具體執行代碼如下：
import java.util.Random;
/**
* @author vincent
* @time 2019-08-07 11:59
*/
public class TopN {
public static int N = 10; //Top10
public static int LEN = 100000000; //1億個整數
public static int arrs[] = new int[LEN];
public static int result[] = new int[N]; //在內存維護一個長度為N的小頂堆
public static int len = result.length;
//堆中元素的有效元素 heapSize<=len
public static int heapSize = len;
public static void main(String[] args) {
//生成隨機數組
for(int i = 0;i<LEN;i++){
arrs[i] = new Random().nextInt(999999999);
}
//構建初始堆
for(int i = 0;i<N;i++){
result[i] = arrs[i];
}
//構建小頂堆
long start =System.currentTimeMillis();
buildMinHeap();
for(int i = N;i<LEN;i++){
if(arrs[i] > result[0]){
result[0] = arrs[i];
minHeap(0);
}
}
System.out.println(LEN+"個數，求Top"+N+"，耗時"+(System.currentTimeMillis()-start)+"毫秒");
print();
}
/**
* 自底向上構建小堆
*/
public static void buildMinHeap(){
int size = len / 2 -1 ; //最後一個非葉子節點
for(int i = size;i>=0;i--){
minHeap(i);
}
}
/**
* i節點為根及子樹是一個小堆
* @param i
*/
public static void minHeap(int i){
int l = left(i);
int r = right(i);
int index = i;
if(l<heapSize && result[l]< result[index]){
index = l;
}
if(r<heapSize && result[r]< result[index]){
index = r;
}
if(index != i){
int t = result[index];
result[index] = result[i];
result[i] = t;
//遞歸向下構建堆
minHeap(index);
}
}
/**
* 返回i節點的左孩子
* @param i
* @return
*/
public static int left(int i){
return 2*i;
}
/**
* 返回i節點的右孩子
* @param i
* @return
*/
public static int right(int i){
return 2*i+1;
}
/**
* 打印
*/
public static void print(){
for(int a: result){
System.out.print(a+",");
}
System.out.println();
}
}
相關推薦
