面试题40. 最小的k个数¶
Tags: Easy
Links: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
输入整数数组 arr
,找出其中最小的 k
个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
示例 1:
输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]
示例 2:
输入:arr = [0,1,2,1], k = 1
输出:[0]
限制:
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
思路一:排序取前K个。
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
sort(arr.begin(), arr.end());
return vector<int>(arr.begin(), arr.begin() + k);
}
};
思路二:堆排序
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
priority_queue<int, vector<int>, greater<int>> pq(arr.begin(), arr.end());
int cnt = 0;
vector<int> res(k);
while (cnt < k) {
res[cnt++] = pq.top(); pq.pop();
}
return res;
}
};
思路三:桶排序,注意到数据的范围在0-10000
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> d(10001);
int n = arr.size();
for (int i = 0; i < n; ++i) ++d[arr[i]];
vector<int> res(k);
int pos = 0;
int cur = 0;
while (pos < k) {
while (cur <= 10000) {
if (d[cur]) {
res[pos] = cur;
--d[cur]; break;
}
else ++cur;
}
++pos;
}
return res;
}
};
思路四:快排