题目

https://www.acwing.com/problem/content/788/

算法思想

利用快速排序的分治思想，在每次数组被分为两部分的时候，判断当前 k 属于左半边还是右半边，如果 k 属于左半边，则只针对左半边继续处理，直到最后收敛到 l >= r 的情况，即可以返回。

解法一

#include <iostream>

const int N = 100010;

int arr[N];

int quick_sort_k(int l, int r, int k) {
    if(l >= r) return arr[l];
    
    int x = arr[l+((r-l)>>1)], i = l - 1, j = r + 1;
    
    while(i < j) {
        do { ++i; } while(arr[i] < x);
        do { --j; } while(arr[j] > x);
        if(i < j) std::swap(arr[i], arr[j]);
    }
    
    if(j + 1 >= k) return quick_sort_k(l, j, k);
    
    return quick_sort_k(j + 1, r, k);
}

int main() {
    int n, k;
    std::cin >> n >> k;
    
    for(std::size_t i = 0; i < n; ++i)
        std::cin >> arr[i];
    
    std::cout << quick_sort_k(0, n - 1, k);
    
    return 0;
}

解法二

#include <iostream>

const int N = 100010;

int arr[N];

int quick_sort_k(int l, int r, int k) {
    if(l >= r) return arr[l];
    
    int i = l - 1, j = r + 1, x = arr[l+((r-l)>>1)];
    int s = l;
    
    while(s < j) {
        if(arr[s] < x) {
            std::swap(arr[s++], arr[++i]);
        } else if(arr[s] > x) {
            std::swap(arr[s], arr[--j]);
        } else {
            ++s;
        }
    }
    
    if((i < k-1) && (j > k-1)) return x;
    
    if(i + 1 >= k) return quick_sort_k(l, i, k);
    
    return quick_sort_k(j, r, k);
}

int main() {
    int n, k;
    std::cin >> n >> k;
    
    for(std::size_t i = 0; i < n; ++i)
        std::cin >> arr[i];
    
    std::cout << quick_sort_k(0, n - 1, k);
    
    return 0;
}

时间复杂度

第一次分区查找，需要针对 n 个元素进行处理，第二次需要针对 n/2 个元素，第三次是 n/4，直到缩小为 1，即

n + n/2 + n/4 + n/8 ... +1

这是等比数列求和，最后的和等于 2n - 1，所以时间复杂度为 O(n)。