面试题40. 最小的k个数
输入整数数组 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
https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
碰到这道题目，我第一想法就是用个大堆。但是心想手撕一个堆似乎还是有些困难。就直接亮出了priority_queue,本想试试看时间限制会不会过，结果还是过了。
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> result;
if (!k) {
return result;
}
priority_queue<int,vector<int>,greater<int>> queue;
for(auto num : arr) {
queue.push(num);
}
while(k--) {
int top = queue.top();
queue.pop();
result.push_back(top);
}
return result;
}
};
结果一不小心竟然还是过了，但是执行的时间来看显然是不理想的。
image.png
所以嘛，leetcode刷过了，面试的时候未必就能过哈。反正我是面试官的话，既然出了这样的题目，肯定是不会让面试者用priority_queue的。
最终还是尝试了手撕了一个堆。
class Solution {
public:
//从i开始堆化
void heapfy(vector<int>& nums,int i, int end) {
while(true) {
int maxPos = i;
int left = 2*i;
int right = 2*i+1;
//在这里我翻了一个错误，一个我经常马虎的问题:将left和maxPos直接进行比较，而不是对应的数组内容比较。
if (left <= end && nums[left] > nums[maxPos]) {
maxPos = left;
}
if (right <= end && nums[right] > nums[maxPos]) {
maxPos = right;
}
if (maxPos == i) { break; }
swap(nums[i], nums[maxPos]);
i = maxPos;
}
}
void buildHeap(vector<int>& nums) {
int size = nums.size()-1;
//从倒数第二排开始堆化操作
for(int i= size/2; i > 0; i--) {
heapfy(nums, i, size);
}
}
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> result(k+1,-1);
if (!k) {
return vector<int>();
}
int i = k;
//k个数进入数组的1~k的位置。
while(i) {
result[i] = arr[i-1];
i--;
}
buildHeap(result);
for(int j=k; j < arr.size(); j++) {
if (arr[j] < result[1]) {
result[1] = arr[j];
heapfy(result, 1, k);
}
}
//堆排序第一个位置需要剔除。
return vector<int>(result.begin()+1,result.end());
}
};
image.png
果然速度就上去了。
