【leetcode每日一刷】2020-03-20，最小的K个数

面试题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

果然速度就上去了。