2019獨角獸企業重金招聘Python工程師標準>>> 
給定一個無序的整型數組arr，找到其中最小的k個數
該題是互聯網面試中十分高頻的一道題，如果用普通的排序算法，排序之后自然可以得到最小的k個數，但時間復雜度高達O(NlogN)，且普通的排序算法均屬于內部排序，需要一次性將全部數據裝入內存，對于求解海量數據的top k問題是無能為力的。
針對海量數據的top k問題，這里實現了一種時間復雜度為O(Nlogk)的有效算法：初始時一次性從文件中讀取k個數據，并建立一個有k個數的最大堆，代表目前選出的最小的k個數。然后從文件中一個一個的讀取剩余數據，如果讀取的數據比堆頂元素小，則把堆頂元素替換成當前的數，然后從堆頂向下重新進行堆調整；否則不進行任何操作，繼續讀取下一個數據。直到文件中的所有數據讀取完畢，堆中的k個數就是海量數據中最小的k個數（如果是找最大的k個數，則使用最小堆）。具體過程請參看如下代碼：
public class FindKMinNums {/*** 維護一個有k個數的最大堆，代表目前選出的最小的k個數** @param read 實際場景中，read提供的數據需要從文件中讀取，這里為了方便用數組表示* @param k* @return*/public static int[] getKMinsByHeap(int[] read, int k) {if (k < 1 || k > read.length) {return read;}int[] kHeap = new int[k];for (int i = 0; i < k; i++) { // 初始時一次性從文件中讀取k個數據kHeap[i] = read[i];}buildHeap(kHeap, k); // 建堆，時間復雜度O(k)for (int i = k; i < read.length; i++) { // 從文件中一個一個的讀取剩余數據if (read[i] < kHeap[0]) {kHeap[0] = read[i];heapify(kHeap, 0, k); // 從堆頂開始向下進行調整，時間復雜度O(logk)}}return kHeap;}/*** 建堆函數** @param arr* @param n*/public static void buildHeap(int[] arr, int n) {for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, i, n);}}/*** 從arr[i]向下進行堆調整** @param arr* @param i* @param heapSize*/public static void heapify(int[] arr, int i, int heapSize) {int leftChild = 2 * i + 1;int rightChild = 2 * i + 2;int max = i;if (leftChild < heapSize && arr[leftChild] > arr[max]) {max = leftChild;}if (rightChild < heapSize && arr[rightChild] > arr[max]) {max = rightChild;}if (max != i) {swap(arr, i, max);heapify(arr, max, heapSize); // 堆結構發生了變化，繼續向下進行堆調整}}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public static void printArray(int[] arr) {for (int i = 0; i <= arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {6, 9, 1, 3, 1, 2, 2, 5, 6, 1, 3, 5, 9, 7, 2, 5, 6, 1, 9};// sorted : { 1, 1, 1, 1, 2, 2, 2, 3, 3, 5, 5, 5, 6, 6, 6, 7, 9, 9, 9 }printArray(getKMinsByHeap(arr, 10));}
}
對于從海量數據(N)中找出TOP K，這種算法僅需一次性將k個數裝入內存，其余數據從文件一個一個讀即可，所以它是針對海量數據TOP K問題最為有效的算法
對于非海量數據的情況，還有一種時間復雜度僅為O(N)的經典算法 —— BFPRT算法，該算法于1973年由Blum、Floyd、Pratt、Rivest和Tarjan聯合發明，其中蘊含的深刻思想改變了世界。
BFPRT算法解決了這樣一個問題：在時間復雜度O(N)內，從無序的數組中找到第k小的數。顯而易見的是，如果我們找到了第k小的數，那么想求arr中最小的k個數，只需再遍歷一遍數組，把小于第k小的數都搜集起來，再把不足部分用第k小的數補全即可。
BFPRT算法是如何找到第k小的數？以下是BFPRT算法的過程，假設BFPRT算法的函數是int select(int[] arr, int k)，該函數的功能為在arr中找到第k小的數，然后返回該數。select(arr, k)的過程如下：
-
將arr中的n個元素劃分成 n/5 組，每組5個元素，如果最后的組不夠5個元素，那么最后剩下的元素為一組（n%5 個元素）。時間復雜度O(1)
-
對每個組進行排序，比如選擇簡單的插入排序，只針對每個組最多5個元素之間的組內排序，組與組之間不排序。時間復雜度 N/5O(1)
-
找到每個組的中位數，如果元素個數為偶數可以找下中位數，讓這些中位數組成一個新的數組，記為mArr。時間復雜度O(N/5)
-
遞歸調用
select(mArr, mArr.length / 2)，意義是找到mArr這個數組的中位數x，即中位數的中位數。時間復雜度T(N/2) -
根據上面得到的x劃分整個arr數組（partition過程），劃分的過程為：在arr中，比x小的都在x左邊，比x大的都在x右邊，x在中間。時間復雜度O(N)
-
假設劃分完成后，x在arr中的位置記為i，關于i與k的相對大小，有如下三種情況：
- 如果 i = k，說明x為整個數組中第k小的數，直接返回。時間復雜度O(1)
- 如果 i < k，說明x處在第k小的數左邊，應該在x的右邊繼續尋找，所以遞歸調用select函數，在右半區尋找第k-i小的數。時間復雜度不超過T(7/10N + 6)
- 如果 i > k，說明x處在第k小的數右邊，應該在x的左邊繼續尋找，所以遞歸調用select函數，在左半區尋找第k小的數。時間復雜度同樣不超過T(7/10N + 6)
上述過程的代碼實現如下：
public class FindKMinNums {/*** 先用BFPRT算法求出第k小的數，再遍歷一遍數組才能求出最小的k個數，時間復雜度O(N)* 需要將所有數據一次性裝入內存，適用于非海量數據的情況** @param arr* @param k* @return*/public static int[] getKMins(int[] arr, int k) {if (k < 1 || k > arr.length) {return arr;}int kthMin = getKthMinByBFPRT(arr, k); // 使用BFPRT算法求得第k小的數，O(N)int[] kMins = new int[k]; // 下面遍歷一遍數組，利用第k小的數找到最小的k個數，O(N)int index = 0;for (int i = 0; i < arr.length; i++) {if (arr[i] < kthMin) { // 小于第k小的數，必然屬于最小的k個數kMins[index++] = arr[i];}}while (index < k) {kMins[index++] = kthMin; // 不足部分用第k小的數補全}return kMins;}/*** 使用BFPRT算法求第k小的數** @param arr* @param k* @return*/public static int getKthMinByBFPRT(int[] arr, int k) {int[] arrCopy = copyArray(arr); // 在得到第k小的數之后還要遍歷一遍原數組，所以并不直接操作原數組return select(arrCopy, 0, arrCopy.length - 1, k - 1); // 第k小的數，即排好序后下標為k-1的數}/*** 拷貝數組** @param arr* @return*/public static int[] copyArray(int[] arr) {int[] arrCopy = new int[arr.length];for (int i = 0; i < arrCopy.length; i++) {arrCopy[i] = arr[i];}return arrCopy;}/*** 在數組arr的下標范圍[begin, end]內，找到排序后位于整個arr數組下標為index的數** @param arr* @param begin* @param end* @param index* @return*/public static int select(int[] arr, int begin, int end, int index) {if (begin == end) {return arr[begin];}int pivot = medianOfMedians(arr, begin, end); // 核心操作：中位數的中位數作為基準int[] pivotRange = partition(arr, begin, end, pivot); // 拿到分區后中區的范圍if (index >= pivotRange[0] && index <= pivotRange[1]) { // 命中return arr[index];} else if (index < pivotRange[0]) {return select(arr, begin, pivotRange[0] - 1, index);} else {return select(arr, pivotRange[1] + 1, end, index);}}/*** 選基準** @param arr* @param begin* @param end* @return*/public static int medianOfMedians(int[] arr, int begin, int end) {int num = end - begin + 1;int offset = num % 5 == 0 ? 0 : 1; // 5個成一組，不滿5個的自己成一組int[] mArr = new int[num / 5 + offset]; // 每組的中位數取出構成中位數數組mArrfor (int i = 0; i < mArr.length; i++) {int beginI = begin + i * 5;int endI = beginI + 4;mArr[i] = getMedian(arr, beginI, Math.min(endI, end));}// 求中位數數組mArr的中位數，作為基準返回return select(mArr, 0, mArr.length - 1, mArr.length / 2);}/*** 在數組arr的下標范圍[begin, end]內，找中位數，如果元素個數為偶數則找下中位數** @param arr* @param begin* @param end* @return*/public static int getMedian(int[] arr, int begin, int end) {insertionSort(arr, begin, end);int sum = begin + end;int mid = (sum / 2) + (sum % 2);return arr[mid];}/*** 這里僅用于對一組5個數進行插入排序，時間復雜度O(1)** @param arr* @param begin* @param end*/public static void insertionSort(int[] arr, int begin, int end) {for (int i = begin + 1; i <= end; i++) {int get = arr[i];int j = i - 1;while (j >= begin && arr[j] > get) {arr[j + 1] = arr[j];j--;}arr[j + 1] = get;}}/*** 優化后的快排partition操作** @param arr* @param begin* @param end* @param pivot* @return 返回劃分后等于基準的元素下標范圍*/public static int[] partition(int[] arr, int begin, int end, int pivot) {int small = begin - 1; // 小區最后一個元素下標int big = end + 1; // 大區第一個元素下標int cur = begin;while (cur < big) {if (arr[cur] < pivot) {swap(arr, ++small, cur++);} else if (arr[cur] > pivot) {swap(arr, --big, cur);} else {cur++;}}int[] range = new int[2];range[0] = small + 1; // 中區第一個元素下標range[1] = big - 1; // 中區最后一個元素下標return range;}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {6, 9, 1, 3, 1, 2, 2, 5, 6, 1, 3, 5, 9, 7, 2, 5, 6, 1, 9};// sorted : { 1, 1, 1, 1, 2, 2, 2, 3, 3, 5, 5, 5, 6, 6, 6, 7, 9, 9, 9 }printArray(getKMins(arr, 10));}
}
關于BFPRT算法為什么在時間復雜度上可以做到穩定的O(N)，可以參考《程序員代碼面試指南》P339或《算法導論》9.3節內容，這里不做證明。
及Viterbi算法)
