本文共 1178 字，大约阅读时间需要 3 分钟。

题目地址：

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

数据范围：

可以用quick select算法将前$k$小的数找出来，然后对前$k$个数排序即可。代码如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;class Solution {
   public:    void quick_select(vector
      
       & v, int l, int r, int idx) {
           if (l >= r) return;        int x = v[l + (r - l >> 1)], i = l, j = r;        while (i <= j) {
               while (v[i] < x) i++;            while (v[j] > x) j--;            if (i <= j) {
                   swap(v[i], v[j]);                i++;                j--;            }        }                if (idx <= j) quick_select(v, l, j, idx);        else if (idx >= i) quick_select(v, i, r, idx);        else return;    }    vector
       
         getLeastNumbers_Solution(vector
        
          input, int k) { quick_select(input, 0, input.size() - 1, k - 1); sort(input.begin(), input.begin() + k); vector
         
           res; for (int i = 0; i < k; i++) res.push_back(input[i]); return res; }};
         
        
       
      
     
    
   

平均时间复杂度$O(n+k\log k)$，平均空间$O(\log n)$。

转载地址：http://xqjs.baihongyu.com/