题目:设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例:
输入: arr = [1,3,5,7,2,4,6,8], k = 4
输出: [1,2,3,4]
class Solution {
public:
void quick_sort(vector<int>&q, int l, int r) {
if (l >= r) { // 判边界, 如果区间中只有一个数字,或没有数字, 就直接return
return;
}
int x = q[(l + r) >> 1]; //分界点
int i = l - 1, j = r + 1;
while (i < j) {
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j) {
swap(q[i], q[j]);
}
}
quick_sort(q, l, j), quick_sort(q, j + 1, r); //递归处理左右两段
}
vector<int> smallestK(vector<int>& arr, int k) {
int n=arr.size();
quick_sort(arr,0,n-1);
return vector(begin(arr), begin(arr)+k);
}
};
【C++】快速选择
无序的话认准 快速选择 nth_element
要求有序就用 部分排序 partial_sort
class Solution {
public:
vector<int> smallestK(vector<int>& arr, int k) {
//nth_element(begin(arr), begin(arr)+k, end(arr));
partial_sort(begin(arr), begin(arr)+k, end(arr));
return vector(begin(arr), begin(arr)+k);
}
};