题目描述

blablabla

样例

#include <iostream>
using namespace std;

const int N = 1e6 + 10;

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

int quick_sort_k(int a[], int l, int r, int k) {
    if (l <= r) {
        int x = a[(l + r) / 2];
        int i = l;
        int j = r;

        while (i <= j) {
            while (a[i] < x) i++;
            while (a[j] > x) j--;
            if (i <= j) {
                swap(a[i], a[j]);
                i++;
                j--;
            }
        }

        if (l <= j && k <= j) {
            return quick_sort_k(a, l, j, k);
        }
        if (i <= r && k >= i) {
            return quick_sort_k(a, i, r, k);
        }
    }
    return a[k];
}

int main() {
    int n, k;
    cin >> n >> k;
    int a[N];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int x = quick_sort_k(a, 0, n - 1, k - 1); 
    cout << x << endl;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla