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

要解决从n个整数中找出k个最小数的问题，可以使用Quick Select算法。该算法通过递归选择数组中的中间元素作为枢轴，将数组划分为左右两部分，然后确定目标元素所在的子数组继续查找。以下是详细的解决方法：

方法思路

解决代码

#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 mid = l + (r - l) / 2;        int x = v[mid];        int 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);        }    }    vector
       
         getLeastNumbers_Solution(vector
        
          input, int k) { if (k == 0) return {}; if (k == input.size()) { sort(input.begin(), input.end()); return input; } 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; }};int main() { vector
          
            input = {1, 2, 3, 4, 5}; int k = 3; Solution sol; vector
           
             result = sol.getLeastNumbers_Solution(input, k); for (int num : result) { cout << num << " "; } return 0;}
           
          
         
        
       
      
     
    
   

代码解释

通过这种方法，我们可以高效地从数组中找出k个最小的数，并按升序排列。

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