查企企官方网站,做网站初中,大庆小程序开发,别人做的网站如何要回服务器1. 题目
设计一个算法#xff0c;找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例#xff1a;
输入#xff1a; arr [1,3,5,7,2,4,6,8], k 4
输出#xff1a; [1,2,3,4]提示#xff1a;
0 len(arr) 100000
0 k min(100000, len(arr))来…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:vectorint smallestK(vectorint arr, int k) {sort(arr.begin(),arr.end());return vectorint(arr.begin(),arr.begin()k);}
};2.2 优先队列堆
class Solution {
public:vectorint smallestK(vectorint arr, int k) {priority_queueint,vectorint,greaterint 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:vectorint smallestK(vectorint arr, int k) {if(arr.empty()||(k0))return {};findkth(arr,k,0,arr.size()-1);return vectorint (arr.begin(), arr.begin()k);}int findkth(vectorint 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,i1,r);return findkth(arr,k,l,i-1);}void selectMid(vectorint 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]);}
};
