设计一个算法,找出数组中最小的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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
vector<int> smallestK(vector<int>& arr, int k) {
sort(arr.begin(),arr.end());
return vector<int>(arr.begin(),arr.begin()+k);
}
};
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;
}
};
参考此篇文章: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]);
}
};