# 11525: 【原1525】第K小的数

### 题目描述

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

## Sample Input

``````8 4
9 5 1 6 2 7 3 8
``````

## Sample Output

``````5
``````

## 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;
}
``````