# 尋找最小的k個數 ## 題目描述 輸入n個整數，輸出其中最小的k個。 ## 分析與解法 ### 解法一 要求一個序列中最小的k個數，按照慣有的思維方式，則是先對這個序列從小到大排序，然后輸出前面的最小的k個數。 至于選取什么的排序方法，我想你可能會第一時間想到快速排序（我們知道，快速排序平均所費時間為`n*logn`），然后再遍歷序列中前k個元素輸出即可。因此，總的時間復雜度：`O（n * log n)+O(k)=O（n * log n）`。 ### 解法二 咱們再進一步想想，題目沒有要求最小的k個數有序，也沒要求最后n-k個數有序。既然如此，就沒有必要對所有元素進行排序。這時，咱們想到了用選擇或交換排序，即： 1、遍歷n個數，把最先遍歷到的k個數存入到大小為k的數組中，假設它們即是最小的k個數； 2、對這k個數，利用選擇或交換排序找到這k個元素中的最大值kmax（找最大值需要遍歷這k個數，時間復雜度為`O（k）`）； 3、繼續遍歷剩余n-k個數。假設每一次遍歷到的新的元素的值為x，把x與kmax比較：如果`x < kmax` ，用x替換kmax，并回到第二步重新找出k個元素的數組中最大元素kmax‘；如果`x >= kmax`，則繼續遍歷不更新數組。 每次遍歷，更新或不更新數組的所用的時間為`O（k）`或`O（0）`。故整趟下來，時間復雜度為`n*O（k）=O（n*k）`。 ### 解法三 更好的辦法是維護容量為k的最大堆，原理跟解法二的方法相似： - 1、用容量為k的最大堆存儲最先遍歷到的k個數，同樣假設它們即是最小的k個數； - 2、堆中元素是有序的，令k1<k2<...<kmax（kmax設為最大堆中的最大元素） - 3、遍歷剩余n-k個數。假設每一次遍歷到的新的元素的值為x，把x與堆頂元素kmax比較：如果`x < kmax`，用x替換kmax，然后更新堆（用時logk）；否則不更新堆。 這樣下來，總的時間復雜度:`O（k+（n-k）*logk）=O（n*logk）`。此方法得益于堆中進行查找和更新的時間復雜度均為：`O(logk)`（若使用解法二：在數組中找出最大元素，時間復雜度：`O（k））`。 ### 解法四 在《數據結構與算法分析--c語言描述》一書，第7章第7.7.6節中，闡述了一種在平均情況下，時間復雜度為`O（N）`的快速選擇算法。如下述文字： - 選取S中一個元素作為樞紐元v，將集合S-{v}分割成S1和S2，就像快速排序那樣 - 如果k <= |S1|，那么第k個最小元素必然在S1中。在這種情況下，返回QuickSelect(S1, k)。 - 如果k = 1 + |S1|，那么樞紐元素就是第k個最小元素，即找到，直接返回它。 - 否則，這第k個最小元素就在S2中，即S2中的第（k - |S1| - 1）個最小元素，我們遞歸調用并返回QuickSelect(S2, k - |S1| - 1)。 此算法的平均運行時間為O(n)。 示例代碼如下： ```cpp //QuickSelect 將第k小的元素放在 a[k-1] void QuickSelect( int a[], int k, int left, int right ) { int i, j; int pivot; if( left + cutoff <= right ) { pivot = median3( a, left, right ); //取三數中值作為樞紐元，可以很大程度上避免最壞情況 i = left; j = right - 1; for( ; ; ) { while( a[ ++i ] < pivot ){ } while( a[ --j ] > pivot ){ } if( i < j ) swap( &a[ i ], &a[ j ] ); else break; } //重置樞紐元 swap( &a[ i ], &a[ right - 1 ] ); if( k <= i ) QuickSelect( a, k, left, i - 1 ); else if( k > i + 1 ) QuickSelect( a, k, i + 1, right ); } else InsertSort( a + left, right - left + 1 ); } ``` 這個快速選擇SELECT算法，類似快速排序的劃分方法。N個數存儲在數組S中，再從數組中選取“中位數的中位數”作為樞紐元X，把數組劃分為Sa和Sb倆部分，Sa<=X<=Sb，如果要查找的k個元素小于Sa的元素個數，則返回Sa中較小的k個元素，否則返回Sa中所有元素+Sb中小的k-|Sa|個元素，這種解法在平均情況下能做到`O(n)`的復雜度。 更進一步，《算法導論》第9章第9.3節介紹了一個最壞情況下亦為O(n)時間的SELECT算法，有興趣的讀者可以參看。 ## 舉一反三 1、谷歌面試題：輸入是兩個整數數組，他們任意兩個數的和又可以組成一個數組，求這個和中前k個數怎么做？ 分析： “假設兩個整數數組為A和B，各有N個元素，任意兩個數的和組成的數組C有N^2個元素。 那么可以把這些和看成N個有序數列： A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3] <=… A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3] <=… … A[N]+B[1] <= A[N]+B[2] <= A[N]+B[3] <=… 問題轉變成，在這N^2個有序數列里，找到前k小的元素” 2、有兩個序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk)，A和B都按升序排列。對于1<=i,j<=k，求k個最小的（ai+bj）。要求算法盡量高效。 3、給定一個數列a1,a2,a3,...,an和m個三元組表示的查詢，對于每個查詢(i，j，k)，輸出ai，ai+1，...，aj的升序排列中第k個數。