如何在 10 億數中找出前 1000 大的數？

2018-10-29 11:20:58 CSDN

作者 | channingbreeze

小史是一個應屆生，雖然學的是電子專業，但是自己業餘時間看了很多互聯網與編程方面的書，一心想進BAT互聯網公司。

之前小史在BAT三家的面試中已經掛了兩家，今天小史去了BAT中的最後一家面試了。

簡單的自我介紹後，面試官給了小史一個問題。

1.面試現場

題目：如何在10億數中找出前1000大的數？

小史：我可以用分治法，這有點類似快排中Partition的操作。隨機選一個數t，然後對整個數組進行Partition，會得到兩部分，前一部分的數都大於t，後一部分的數都小於t。

小史：如果說前一部分總數大於1000個，那就繼續在前一部分進行Partition尋找。如果前一部分的數小於1000個，那就在後一部分再進行Partition，尋找剩下的數。

小史：首先，Partition的過程，時間是o(n)。我們在進行第一次Partition的時候需要花費n，第二次Partition的時候，數據量減半了，所以只要花費n/2，同理第三次的時候只要花費n/4，以此類推。而n+n/2+n/4+......顯然是小於2n的，所以這個方法的漸進時間只有o(n)。

（注：這裡的時間複雜度計算只是簡化計算版，真正嚴謹的數學證明可以參考算法導論相關分析。）

半分鐘過去了。

小史一時慌了神。

他回憶起了之前呂老師給他講解bitmap時的一些細節。突然有了一個想法。

小史在紙上畫了畫。

理解了算法之後，小史的代碼寫起來也是非常快，不一會兒就寫好了：

TopN.java：

/**
 * @author xiaoshi on 2018/10/14.
 */
public class TopN {
 // 父節點
 private int parent(int n) {
 return (n - 1) / 2;
 }
 // 左孩子
 private int left(int n) {
 return 2 * n + 1;
 }
 // 右孩子
 private int right(int n) {
 return 2 * n + 2;
 }
 // 構建堆
 private void buildHeap(int n, int[] data) {
 for(int i = 1; i < n; i++) {
 int t = i;
 // 調整堆
 while(t != 0 && data[parent(t)] > data[t]) {
 int temp = data[t];
 data[t] = data[parent(t)];
 data[parent(t)] = temp;
 t = parent(t);
 }
 }
 }
 // 調整data[i]
 private void adjust(int i, int n, int[] data) {
 if(data[i] <= data[0]) {
 return;
 }
 // 置換堆頂
 int temp = data[i];
 data[i] = data[0]; 

 data[0] = temp;
 // 調整堆頂
 int t = 0;
 while( (left(t) < n && data[t] > data[left(t)])
 || (right(t) < n && data[t] > data[right(t)]) ) {
 if(right(t) < n && data[right(t)] < data[left(t)]) {
 // 右孩子更小，置換右孩子
 temp = data[t];
 data[t] = data[right(t)];
 data[right(t)] = temp;
 t = right(t);
 } else {
 // 否則置換左孩子
 temp = data[t];
 data[t] = data[left(t)];
 data[left(t)] = temp;
 t = left(t);
 }
 }
 }
 // 尋找topN，該方法改變data，將topN排到最前面
 public void findTopN(int n, int[] data) {
 // 先構建n個數的小頂堆
 buildHeap(n, data);
 // n往後的數進行調整
 for(int i = n; i < data.length; i++) {
 adjust(i, n, data);
 }
 }
 // 打印數組
 public void print(int[] data) {
 for(int i = 0; i < data.length; i++) {
 System.out.print(data[i] + " ");
 }
 System.out.println();
 }
}

友情提示：可左右滑動

Main.java：

import java.util.Random;
/**
 * @author xiaoshi on 2018/10/14.
 */
public class Main {
 public static void main(String[] args) {
 TopN topN = new TopN();
 // 第一組測試
 int[] arr1 = new int[]{56, 30, 71, 18, 29, 93, 44, 75, 20, 65, 68, 34};
 System.out.println("原數組：");
 topN.print(arr1);
 topN.findTopN(5, arr1);
 System.out.println("調整後數組：");
 topN.print(arr1);
 // 第二組測試
 int[] arr2 = new int[1000];
 for(int i=0; i arr2[i] = i + 1;
 }
 System.out.println("原數組：");
 topN.print(arr2);
 topN.findTopN(50, arr2);
 System.out.println("調整後數組：");
 topN.print(arr2);
 // 第三組測試
 Random random =new Random();
 int[] arr3 = new int[1000];
 for(int i=0; i arr3[i] = random.nextInt();
 }
 System.out.println("原數組：");
 topN.print(arr3);
 topN.findTopN(50, arr3);
 System.out.println("調整後數組：");
 topN.print(arr3);
 }
}

友情提示：可左右滑動

運行結果：

原數組：
56 30 71 18 29 93 44 75 20 65 68 34 
調整後數組：
65 68 71 75 93 18 29 30 20 44 56 34 
原數組：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 
調整後數組：
951 952 955 954 953 956 957 963 968 964 972 961 979 959 958 967 966 969 974 965 970 973 988 962 983 993 986 981 987 992 960 976 1000 982 978 977 975 985 984 990 971 997 996 991 989 999 998 980 994 995 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 
原數組：
835636999 -90522479 -769818338 -1416245398 1041573706 1812203535 896607110 1789246766 1774883884 26722194 -418633859 1344767118 1570967674 1316806558 -1435502178 1473470755 -918439629 1869702742 2101404773 -1296472335 649689400 1153902366 -1052670714 498645159 -1530905537 -1159220094 -154125959 -868393434 -504505075 -1106082731 -494609447 -1406763201 -750828828 -342445539 -744595730 -1920006464 -1230413255 -1426324562 -1277878264 474935729 -2029054806 447026196 -1121975794 -1448358181 1957166126 1336854710 …… 
調整後數組：
1960093727 1964906931 1970688292 1975808864 1981745799 1991241336 2022661667 1981095418 1998580270 1988169309 2008783098 2027208746 2136972032 2062185334 2058314391 2003774732 2022245178 2022674254 2076406457 2024695646 2106449320 2016192325 2039153729 2043057170 2042482994 2138695524 2139809413 2121618159 2067898415 2122335504 2101895240 2100462015 2054036800 2037921932 2067998974 2117710597 2133594097 2101404773 2077564852 2033907579 2035097590 2108250457 2122256662 2138496647 2088084171 2107415856 2077919162 ……

友情提示：可左右滑動

（注：由於1000個數字符過多，超了微信文章限制，結果進行了省略，大家可以本地運行查看結果）

面試官看了一下。

小史熟練地介紹起了自己的項目，由於準備充分，小史聊起來遊刃有餘。面試官問的幾個問題也進行了詳細的解釋。

小史走後，面試官在系統中寫下了面試評語：

2.遇見呂老師

小史回到學校哼著歌走在校園的路上，正好碰到呂老師。

小史把面試情況和呂老師說了一下。

小史：感悟還挺深的。雖然平時做過TopN的問題，知道分治法時間更少。但是碰到具體問題的時候還是要具體分析，這種大數據量的情況下反而用堆會更快。

作者簡介：channingbreeze，國內某互聯網公司全棧開發。

分享到:

閱讀更多 CSDN 的文章

關鍵字: 百度億數技術