🎈 原创

洛谷P1923 求第k小的数

题目描述

输入 nn(n<5000000n<5000000 且 nn 为奇数) 个数字 a_i(0<a_i<10^9)a**i(0<a**i<109) ，输出这些数字的第 kk 小的数。最小的数是第 0 小。

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

输入格式

无

输出格式

无

输入输出样例

输入 #1

5 1
4 3 2 1 5

输出 #1

2

---

题目很简单，做法也有很多。

1.STL函数nth_element

nth_element(数组名,数组名+第k小元素,数组名+元素个数)

nth_element(a,a+k,a+n);//使第k小整数就位 
printf("%d",a[k]);//调用第k小整数

2.快排找第k大（分而治之）

首先在数组中随机选择一个数（这里选第一个），利用快排的方式将这个数放到正确的顺序位置。然后返回这个位置，这个位置代表了这个数是第几大。

外面再套一层函数，利用二分，通过返回的数大小确定新的区间，再递归调用寻找

#include <iostream>
#include <algorithm>
using namespace std;

long long int num[5000001];
int quicksort(int left, int right);
void find(int left, int right, int K);

int main(int argc, const char *argv[])
{
    int N, K;
    ios::sync_with_stdio(false);
    cin >> N >> K;
    for(int i = 0; i < N; i++)
        cin >> num[i];
    find(0, N - 1, K);

    return 0;
}

int quicksort(int left, int right)
{
    long long int mid = num[left];
    while(left < right)
    {
        while(left < right && mid <= num[right])
            right--;
        num[left] = num[right];
        while(left < right && num[left] <= mid)
            left++;
        num[right] = num[left];
    }
    num[left] = mid;
    return left;
}

void find(int left, int right, int K)
{
    int temp = quicksort(left, right);
    if(K == temp)
        cout << num[K];
    else if(temp > K)
        find(left, temp - 1, K);
    else
        find(temp + 1, right, K);
}