題目：輸入N個數字，找出其中最小的K個數。

思路：維護一個數組KMin，長度為K，存放最小的K個數。遍歷原始數組的過程中，如果KMin不滿，就直接在后邊插入新的數字；如果KMin滿了，就要找到其中最大的數字，和當前遍歷原始數組時遇到的數字進行比較，決定是否更新。由于每次都要獲得KMin中最大的數字，所以可以把KMin用一個大頂堆來實現，當KMin滿了的時候，就建堆，之后在每次遍歷時，都用當前遍歷得到的元素與KMin的堆頂比較，決定是否更新，如果更新，就維護堆。其中建堆過程和維護堆的過程共用一個函數AdjustHeap來描述。算法用C/C++實現。

void AdjustHeap(int* const arr, const int length){for(int i = length / 2 - 1; i >= 0; i--){int temp = arr[i];int k = 0;for(int j = i * 2 + 1; j < length; j = k * 2 + 1){k = j;if(j + 1 < length)k = arr[j] > arr[j + 1] ? j : j + 1;if(arr[k] > arr[i]){arr[(j - 1) / 2] = arr[k];arr[k] = temp;}else break;}} }int* GetKMin(int* const arr, const int length, const int K){if(K <= 0) return NULL;int* KMin = new int[K];for(int i = 0; i < length; i++){if(i <= K)KMin[i] = arr[i];if(i == K)AdjustHeap(KMin, K);if(i > K)if(arr[i] < KMin[0]){KMin[0] = arr[i];AdjustHeap(KMin, K);}}return KMin; }

　　

測試代碼：

int main(){const int K = 5;const int B = 10;static int TestBase[B] = {6, 2, 20, 13, 9, 11, 7, 5, 1, 8};static int TestBase2[B] = {6, 2, 20, 13, 9, 11, 7, 5, 1, 6};int i = 0;for(i = 0; i < B; i++) cout << TestBase[i] << " ";cout << endl;int * KMin = GetKMin(TestBase, B, K);if(KMin)for(i = 0; i < K && i < B; i++) cout << KMin[i] << " ";cout << endl;return 0; }

　　

測試用例：

K = 5， B = 10；

K = 1， B = 10；

K = 0， B = 10；

K = -1， B = 10；

K = 15， B = 10；

還可以使用TestBase和TestBase2分別測試原始數組中是否有重復元素。

轉載于:https://www.cnblogs.com/superpig0501/p/3980513.html

總結

以上是生活随笔為你收集整理的剑指Offer——面试题30：最小的K个数的全部內容，希望文章能夠幫你解決所遇到的問題。

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