求第 k 小的数

zhyyyyy115 / 2023-05-03 / 原文

【深基9.例4】求第 k 小的数

题目描述

输入 \(n\)（\(1 \le n < 5000000\) 且 \(n\) 为奇数）个数字 \(a_i\)（\(1 \le a_i < {10}^9\)），输出这些数字的第 \(k\) 小的数。最小的数是第 \(0\) 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

题解1

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6+5;
int n, k;
int a[N];
void quick_sort(int l, int r) {
    int i = l, j = r;
    int c = a[l];
    while(i < j) {
        while(i < j && a[j] > c) j--;
        a[i] = a[j];
        while(i < j && a[i] < c) i++;
        a[j] = a[i];
    }
    a[i] = c;
    if(k == i) {
        cout << c << "\n";
    } else if(k < i) {
        quick_sort(l, i-1);
    } else {
        quick_sort(i+1, r);
    }
} 
int main() {
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }        
    quick_sort(0, n-1);
    return 0;
}

题解2

在 STL 里有一个神奇的函数 nth_element。
它的用法是 nth_element(a+x,a+x+y,a+x+len);
nth_element 的时间复杂度是 O(n)O(n) 的，不过 STL 常数普遍较大
执行之后数组 a 下标 x 到 x+y−1 的元素都小于 a[x+y]，下标 x+y+1 到 x+len−1 的元素都大于 a[x+y]，但不保证数组有序。此时 a[x+y] 就是数组区间 x 到 x+len−1 中第 y 小的数，当然也可以自己定义 cmp 函数。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6+5;
int n, k;
int a[N];
int main()
{
	int n;
	cin >> n >> k;
	for(int i=0;i<n;i++) cin >> a[i];
	nth_element(x,x+k,x+n); 
	printf("%d",x[k]);
}