题目描述

输入 n 个整数，找出其中最小的 k 个数。

注意：

数据保证 k 一定小于等于输入数组的长度;
输出数组内元素请按从小到大顺序排序;

样例

输入：[1,2,3,4,5,6,7,8] , k=4

输出：[1,2,3,4]

排序

最简单直接能想到的方法，这里不写了

优先队列

C++代码

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> pq;
        for (int x: input) pq.emplace(-1*x);
        vector<int> result;
        for (int i = 0; i < k; i++)
        {
            result.push_back(-1*pq.top());
            pq.pop();
        }
        return result;
    }
};

Python代码

class Solution(object):
    def getLeastNumbers_Solution(self, input, k):
        """
        :type input: list[int]
        :type k: int
        :rtype: list[int]
        """
        import heapq
        result = []
        heapq.heapify(input)
        for i in range(k):
            result.append(heapq.heappop(input))
        return result