Ex40 最小的k个数

题目描述

输入整数数组 arr，找出其中最小的 k个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

解题思路

使用一个最大堆（最大的数字在堆顶），存储k的元素。遍历所有的数字，当其小于最大堆的top时，则将top弹出，然后压入此数字。

代码1

class Solution
{
public:
  std::vector<int>
  getLeastNumbers (std::vector<int> &arr, int k)
  {
    if (k <= 0) 
      return std::vector<int>();
    if (arr.size () <= k)
      return std::vector<int> (arr);
    std::priority_queue<int> pq (arr.begin (), arr.begin () + k);
    for (int i = k; i < arr.size (); ++i)
      {
        if (arr[i] < pq.top ())
          {
            pq.pop ();
            pq.push (arr[i]);
          }
      }
    std::vector<int> rtn (0, pq.size ());
    while (!pq.empty ())
      {
        rtn.push_back (pq.top ());
        pq.pop ();
      }
    return rtn;
  }
};

结果1

执行结果：通过

执行用时：112 ms, 在所有 C++ 提交中击败了36.98%的用户

内存消耗：19.6 MB, 在所有 C++ 提交中击败了19.01%的用户

代码2

结果2