從1億個數里面找出前100個最大的

這個題目應該是一些大公司面試題中經常被問到的，這里我給出一種做法，至于面試官滿不滿意我就不知道了。我們知道，這種找出前多少個最大或者最小的最適合用堆排序(對堆排序不熟悉的讀者可以參考為的這篇博客：堆排序)。但是如果我們用1億個數去建堆并調整，當然時間復雜度是不允許的。題目中要求前100個大的，那么我們就只用100個數建堆，而且是建立成最小堆。剩下的1億減100個數依次和堆頂元素比較，如果比堆頂元素小，那么不管它。如果比堆頂元素大，就用這個元素把堆頂元素替換掉，然后調整堆，繼續保持最小堆的性質。直到剩下的所有元素都和堆頂元素比較完畢。那么堆中的100個數就是最大的。假設一共是n個數，找前m個大的。第一次建堆并調整的時間大約為mlog(m)，那么對于剩下的每個元素，最壞的情況下就是每個都調整堆，堆調整一次的時間復雜度為log(m)，所以總的時間復雜度為（n-m）log(m) + mlog(m) = nlog(m)

public class Demo {public static void main(String[] args) {int n = 10000;int m = 10;int[] arr = new int[n];for(int i = 0; i < n; i++) {arr[i] = i + 1;}print(arr,n);for(int i = 0; i < m; i++) {System.out.print(arr[i] + " ");}}//剩下的n-m個數與堆頂元素依次比較，并調整堆結構public static void print(int[] arr, int m) {//把前m個數建成最小堆 createSmallHeap(arr,m); //把剩下的arr.length-m個數字依次與最小堆的堆頂元素比較//如果比堆頂元素大，那么就替換為堆頂，然后對堆頂進行調整。//當所有的元素遍歷一遍后，堆中元素就是前m個最大的。for(int i = m; i < arr.length; i++) {if(arr[i] > arr[0]) {arr[0] = arr[i];adjustHeap(arr,m,0);}}}//新建堆public static void createSmallHeap(int[] arr, int m) {for(int i = m / 2 - 1; i >= 0; i--) {adjustHeap(arr, m, i);}}//調整為最小堆public static void adjustHeap(int[] arr, int m, int i) {int temp = arr[i];for(int k = 2 * i + 1; k < m; k = 2 * k + 1) {if(k + 1 < m && arr[k + 1] < arr[k]) k++;if(temp > arr[k]) {arr[i] = arr[k];i = k;}}arr[i] = temp;} }

?

posted @ 2018-08-16 15:51 neu_張康 閱讀( ...) 評論( ...) 編輯 收藏

總結

以上是生活随笔為你收集整理的从1亿个数里面找出前100个最大的的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。