题解 | #最小的K个数#
最小的K个数
http://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
我看到很多人都是使用的快速排序，这里分享一个使用最大堆的方式：
运行时间：3ms
占用内存：512KB
class Solution {
public:
// miniK 使用最大堆
void max_heapfiy(vector<int>& input, int begin, int end) {
int l = begin * 2 + 1;
int r = begin * 2 + 2;
size_t largest = begin;
if(l < end && input[l] > input[largest]) largest = l;
if(r < end && input[r] > input[largest]) largest = r;
if(largest != begin) {
swap(input[begin], input[largest]);
max_heapfiy(input, largest, end);
}
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
// 构建堆
for(int i = k / 2; i >= 0; --i) max_heapfiy(input, i, k);
for(int i = k; i < input.size(); ++i) {
if(input[i] < input[0]) {
swap(input[0], input[i]);
max_heapfiy(input, 0, k);
}
}
return {input.begin(), input.begin() + k};
}
}; 这里唯一需要特别注意的是第十八行一定要是 int i = k 因为如果更小的话会导致堆顶与堆底元素发生交换，这时因为顶点的左右孩子没有变化，因此不会触发维护算法。这时就出错了。
比较遗憾的是看来测试集中没有大数据集，因此最大堆的好处体现不出来。反而比快速排序还要慢：
查看8道真题和解析