题目描述
给定一个长度为n的整数数列,以及一个整数k,请用快速选择算法求出数列的第k小的数是多少。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整数数列。
输出格式
输出一个整数,表示数列的第k小数。
数据范围
1≤n≤100000,
1≤k≤n
样例
输入样例:
5 3
2 4 1 5 3
输出样例:
3
我的思路
快排的整体思路,首先选择序列中的一个数可以是a[l], a[l + r >> 1], a[r];然后把小于等于x(选择的数)放在它的左边,大于等于x的放在它的右边,接着再去递归排序x的左半边序列和右半边序列。快排的关键点在于边界的处理,当x = a[l]时,递归的区间应该为(l, j)和(j + 1, r);当x = a[r]时,递归的区间应该为(1, i - 1)和(i, r);
第二次思路
总体来说还是快排的思路,但是每次做完一次排序(即 i >= j), 判断k 是否 小于或等于 j - l + 1(我取得标记是a[l]), 若是不等式成立则递归执行左半边的区间[l, j]否则执行右半区间[j + 1, r],若是执行右区间需要更新k, 即:k = k - (j - l + 1);这样相对与我第一次的思想时间复杂度减少了从O(n * log n) 变成了 O(n), 极限情况是2 * n 的时间复杂度。
That’s all.
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + 50;
int a[maxn];
inline void quick_sort(int p[], int l, int r) {
if(l >= r) return;
int i = l - 1, j = r + 1, x = p[l];
while(i < j) {
do i++; while(p[i] < x);
do j--; while(p[j] > x);
if(i < j) swap(p[i], p[j]);
else break;
}
quick_sort(p, l, j);
quick_sort(p, j + 1, r);
}
int main(void) {
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
quick_sort(a, 1, n);
int i;
for(i = 1; i <= n && i <= k; i++);
printf("%d\n", a[i - 1]);
return 0;
}
第二次 代码
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
inline int quick_sort(int l, int r, int k) {
if(l >= r) return a[l];
int i = l - 1, j = r + 1, x = a[l];
while(i < j) {
do i ++; while(a[i] < x);
do j --; while(a[j] > x);
if(i < j) swap(a[i], a[j]);
else break;
}
int sl = j - l + 1;
if(k <= sl) quick_sort(l, j, k);
else quick_sort(j + 1, r, k - sl);
}
int main(void) {
int n, k;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
printf("%d\n", quick_sort(1, n, k));
return 0;
}