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

c plus

  • 排序法

    1. class Solution {
    2. public:
    3.   vector<int> getLeastNumbers(vector<int>& arr, int k) {
    4.       vector<int> ret(k, 0);
    5.       sort(arr.begin(), arr.end());
    6.       for (int i = 0; i < k; i++) {
    7.           ret.push_back(arr[i]);
    8.       }
    9.       return ret;
    10.   }
    11. };

  • 大根堆

大优先队列，比较最顶点的值，如果比顶点值小，就Push 进队列，顶点pop掉。

  1. class Solution {
  2. public:
  3.     vector<int> getLeastNumbers(vector<int>& arr, int k) {
  4.         vector<int> ret(k, 0);
  5.         if (k == 0)    return ret;
  6.         priority_queue<int> p;
  7.         for (int i = 0; i < k; ++i) p.push(arr[i]);
  8.         for (int i = k; i < arr.size(); ++i) {
  9.             if (arr[i] < p.top()) {
  10.                 p.pop();
  11.                 p.push(arr[i]);
  12.             }
  13.         }
  14.         for (int i = 0; i < k; ++i) {
  15.             ret[i] = p.top();
  16.             p.pop();
  17.         }
  18.         return ret;
  19.     }
  20. };