1. 題目

設計一個算法，找出數組中最小的k個數。以任意順序返回這k個數均可。

示例： 輸入： arr = [1,3,5,7,2,4,6,8], k = 4 輸出： [1,2,3,4]提示： 0 <= len(arr) <= 100000 0 <= k <= min(100000, len(arr))

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/smallest-k-lcci
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 排序

class Solution { public:vector<int> smallestK(vector<int>& arr, int k) {sort(arr.begin(),arr.end());return vector<int>(arr.begin(),arr.begin()+k);} };

2.2 優先隊列（堆）

class Solution { public:vector<int> smallestK(vector<int>& arr, int k) {priority_queue<int,vector<int>,greater<int>> q;//小頂堆for(auto& a : arr)q.push(a);arr.clear();while(k--){arr.push_back(q.top());q.pop();}return arr;} };

2.3 快排劃分

參考此篇文章：LeetCode 215. 數組中的第K個最大元素（快速排序）

class Solution { public:vector<int> smallestK(vector<int>& arr, int k) {if(arr.empty()||(k==0))return {};findkth(arr,k,0,arr.size()-1);return vector<int> (arr.begin(), arr.begin()+k);}int findkth(vector<int>& arr, int& k, int l, int r){selectMid(arr,l,r);int p = arr[l];int i = l, j = r;while(i < j){while(i < j && arr[j] > p)j--;swap(arr[i],arr[j]);while(i < j && arr[i] <= p)i++;swap(arr[i],arr[j]);}if(i == k)return i;else if(i < k)return findkth(arr,k,i+1,r);return findkth(arr,k,l,i-1);}void selectMid(vector<int>& arr, int& l, int& r){int mid = l+((r-l)>>1);if(arr[mid] > arr[r])swap(arr[mid],arr[r]);if(arr[l] > arr[r])swap(arr[mid],arr[r]);if(arr[mid] > arr[l])swap(arr[mid],arr[l]);} };

總結

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 17.14. 最小K个数（快排划分O(n)）的全部內容，希望文章能夠幫你解決所遇到的問題。

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