LeetCode-面试题40. 最小的k个数
程序员文章站
2024-03-15 09:08:35
...
面试题40. 最小的k个数
解
方法一:暴力法
直接排序
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
sort(arr.begin(), arr.end());
vector<int>ret(arr.begin(), arr.begin() + k);
return ret;
}
};
方法二:堆
利用大根堆来找Top k
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int>ret(k, 0);
if (k == 0) {
return ret;
}
priority_queue<int>maxHeap;
for (int i = 0; i < k; i++) {
maxHeap.push(arr[i]);
}
for (int i = k; i < (int)arr.size(); i++) {
if (maxHeap.top() > arr[i]) {
maxHeap.pop();
maxHeap.push(arr[i]);
}
}
for (int i = 0; i < k; i++) {
ret[i] = maxHeap.top();
maxHeap.pop();
}
return ret;
}
};
方法三:快排
利用快速排序思想实现快速查找
class Solution {
int partition(vector<int>& nums, int left, int right) {
int v = nums[left];
int i = left, j = right + 1;
while (true) {
while (++i <= right && nums[i] < v);
while (--j >= left && nums[j] > v);
if (i >= j) {
break;
}
swap(nums[i], nums[j]);
}
swap(nums[j], nums[left]);
return j;
}
vector<int> quickSearch(vector<int>& nums, int left, int right, int k) {
int i = partition(nums, left, right);
if (i == k) {
vector<int>ret(nums.begin(), nums.begin() + k + 1);
return ret;
}
return i > k ? quickSearch(nums, left, i - 1, k) : quickSearch(nums, i + 1, right, k);
}
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if (k == 0) {
vector<int>ret(k, 0);
return ret;
}
return quickSearch(arr, 0, arr.size() - 1, k - 1);//数组的第k-1位
}
};