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

???????k???????????????????????????????????????????

????

??????????????????????k????????????

???????????O(n log n)????????

????

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
class Solution {
public:
    void GetMinKthNumbers(vector
      
       & input, int k) {
        int n = input.size();
        if (k > n || n <= 0 || k <= 0) {
            cout << -1 << endl;
            return;
        }
        int start = 0;
        int end = n - 1;
        int index = partition(input, start, end);
        while (index != k - 1) {
            if (index > k - 1) {
                end = index - 1;
                index = partition(input, start, end);
            } else {
                start = index + 1;
                index = partition(input, start, end);
            }
        }
        cout << input[index] << endl;
    }
public:
    int partition(vector
       
        & input, int start, int end) {
        int n = input.size();
        if (n <= 1) return start;
        int i = start;
        int j = end;
        while (i < j) {
            while (i < j && input[i] <= input[j]) {
                ++i;
            }
            if (i < j) {
                swap(input[i], input[j]);
                ++i;
            }
            --j;
        }
        return i;
    }
};
int main() {
    vector
        
          input; string s = "{4,5,1,6,2,7,3,8}"; for (char ch : s) { if (ch == ',') continue; input.push_back(ch - '0'); } int k = 0; cin >> k; Solution solution; solution.GetMinKthNumbers(input, k); system("pause"); return 0; }
        
       
      
     
    
   

??

??????????????????????????O(n log n)?????????k?????