11525: 【原1525】第K小的数

题目

题目描述

author: 金耀楠 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1525 ## Description

输入n个整数，找出其中第K小的数。例如输入9,5,1,6,2,7,3,8这8个数字，则第4小的数字5。

Input Format

每个测试案例包括2行：

第一行为2个整数n，k，表示数组的长度。

第二行包含n个整数，表示这n个数，数组中的数的范围是[0,200000000]。

Output Format

对应每个测试案例，输出第k小数。

Sample Input

8 4
9 5 1 6 2 7 3 8

Sample Output

5

Limit

时间限制：20秒。 单点时限：2秒。 前30%的评测用例满足：1 ≤ k ≤ n ≤ 1000。 前60%的评测用例满足：1 ≤ k ≤ n ≤ 1000000。 所有评测用例都满足：1 ≤ k ≤ n ≤ 3000000。

ligongzzz's solution

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

vector<int> vdata;
int n;

int find_k(int start, int end, int k) {
    int key = vdata[start], l = start, r = end - 1;
    bool status = true;
    while (l < r) {
        if (status)
            if (key > vdata[r]) {
                vdata[l] = vdata[r];
                status = false;
                ++l;
            }
            else
                --r;
        else
            if (key < vdata[l]) {
                vdata[r] = vdata[l];
                status = true;
                --r;
            }
            else
                ++l;
    }
    vdata[l] = key;
    if (k > l - start)
        return find_k(l + 1, end, k - l + start - 1);
    else if (k < l - start)
        return find_k(start, l, k);
    else
        return vdata[l];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int k;
    cin >> n >> k;
    vdata.resize(n);

    for (int i = 0; i < n; ++i)
        cin >> vdata[i];

    cout << find_k(0, n, k - 1);

    return 0;
}

yyong119's solution

#include <algorithm>
#include <cstdio>
using namespace std;
const int MAX_N = 3000010;
int a[MAX_N];
int main() {

    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    sort(a, a + n);
    printf("%d\n", a[k - 1]);
    return 0;
}