题目链接

题意

如题目。

题解

快排解决

因为没有要求要有序的返回TopK，那么该题可以利用快排进行划分排序的性质。即每次快排完成一次划分，判断当前划分位置和所需K的大小，来决定是终止划分还是继续划分。

大根堆

取数组中的前K个树，建一个大小为K的大根堆。然后将剩余的数和大根堆堆顶的数进行比较，若大于堆顶数则跳过。否则，先将堆顶元素弹出，再将该数插入堆中。

代码

快排题解

  1. class Solution {
  2. public:
  3.     vector<int> getLeastNumbers(vector<int>& arr, int k) {
  4.         quickSort(arr, 0, arr.size()-1, k);
  5.         vector<int> res;
  6.         for (int i = 0; i < k; i++) {
  7.             res.push_back(arr[i]);
  8.         }
  9.         return res;
  10.     }
  11. private:
  12.     void quickSort(vector<int>& arr, int l , int r, int k) {
  13.         if (l > r) return;
  14.         int st = l, ter = r;
  15.         while (st < ter) {
  16.             while (arr[ter] >= arr[l] && st < ter) ter--;
  17.             while (arr[st] <= arr[l] && st < ter) st++;
  18.             swap(arr[ter], arr[st]);
  19.         }
  20.         swap(arr[l], arr[st]);
  21.         if (st+1 == k) return;
  22.         else if (st+1 < k)quickSort(arr, st + 1, r, k);
  23.         else quickSort(arr, l, st-1, k);
  24.     }
  25. };