AcWing 786. 第k个数

原题链接：https://www.acwing.com/problem/content/788/

k-选取问题的核心依然是快速划分算法partition()，可以保证在的时间内完成k-选取。

#include <iostream>

void swap(int& x, int& y) {
    if (x == y) return;
    x ^= y; y ^= x; x ^= y;
}

int partition(int nums[], int left, int right) {
    int i = left, j = right - 1;
    swap(nums[left], nums[(left + right) >> 1]);
    int pivot = nums[left];
    while (i < j) {
        while (i < j && pivot < nums[j]) j--;
        if (i < j) nums[i++] = nums[j];
        while (i < j && nums[i] < pivot) i++;
        if (i < j) nums[j--] = nums[i];
    }
    nums[i] = pivot;
    return i;
}

int k_select(int nums[], int left, int right, int k) {
    while (left < right) {
        int pos = partition(nums, left, right);
        if (k < pos) { right = pos; }
        else if (k > pos) { left = pos; }
        else return nums[pos];
    }
    return nums[left];
}


int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int nums[n];
    N = n;
    for (int i = 0; i < n; i++) scanf("%d ", &nums[i]);
    int k_th = k_select(nums, 0, n, k - 1);
    printf("%d", k_th);
}