JZ29 题解 | #最小的K个数#

题意分析

根据题目我们可以知道，就是给出一个数组，让我们求出最小的k个数字所构成的数组。如果不足以构成k个数字，那么就返回一个空数组。
样例解释，这里我用的是第二种解法

思路分析

解法一

根据题目的要求，需要我们求出最小的k个数字，对于这种有大小顺序的情况，我们很容易想到的就是先进行排序，然后我们直接遍历最小的k个数字即可。排序的话我们可以调用库函数。

时间复杂度 $O(Nlog_N)$ ,空间复杂度为O(N)

class Solution {
public:
  vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
      int n=input.size();
      vector<int> ans;
      // 先判断是否符合要求
      if(n<k){   
          return ans;
      }
      // 直接排序即可
      sort(input.begin(),input.end());  
      for(int i=0;i<k;i++){
          ans.push_back(input[i]);
      }
      return ans;
  }
};

解法二

然后我们继续观察是否可以继续进行优化，我们发现，在我们C++里面，排序的话我们不仅可以使用库函数，同时也可以利用一些STL里面的一些容器进行排序。所以我们可以发现其实我们可以用一个大根堆来维护最小的k个数字，我们依次将n个数字放入堆中，然后如果此时堆中的数字超过k个，那么就说明此时堆中最大的数字一定不属于最小的k个数字里面，所以我们可以将堆顶的元素进行出堆。最后留下的就是我们想要求的了。在这里为了方便，我使用的是优先队列进行模拟大根堆进行维护。
这里补充一下大根堆和小根堆的知识点，大根堆就是对于每个结点，其根结点最大；小根堆就是最小的放到根节点里面，每插入一个数字，然后就可以根据堆的情况进行调整。这里可以手动实现，也可以用STL里面的优先队列。这样就省去了我们对堆的调整，每次操作直接取堆顶就行了。这里注意的是如果自己实现堆的话可能堆的情况不止一种，但是不会影响最后的结果。，可以结合下面这个图进行理解。

图片说明

同时我们发现，其实初始化的那个数组可以用来再利用，这样我们就不需要另外开一个数组了。

时间复杂度 $O(Nlog_K)$ ，空间复杂度为O(1)

class Solution {
public:
  priority_queue<int> q;
  vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
      // 将数组里面的数字都放入一个优先队列里面
      for(auto x:input){
          q.push(x);
          if(q.size()>k){
              q.pop();
          }
      }
      // 对input数组
      input.clear();
      // 如果达不到k个数字
      if(q.size()<k){  
          return input;
      }
      while(!q.empty()){
          input.push_back(q.top());
          q.pop();
      }
      return input;
  }
};