7-5 sdut-C语言实验-第k小的数
分数 20
全屏浏览
切换布局
作者 马新娟
单位 山东理工大学
现有一个包含n个整数（1<=n<=900000）的无序序列(保证序列内元素各不相同)，输入一个整数k（1<=k<=n）,请用较快的方式找出该序列的第k小数并输出。
###输入格式:
第一行先输入两个整数，n和k。
接下来是一行输入n个由空格分开的互不相同的整数num(1<=num<=90000000)。
###输出格式:
输出该组数据中第k小的数num。
###输入样例:
1. 6 4 2. 3 2 5 1 4 6
###输出样例:
4
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
#include<stdio.h> #include<stdlib.h> void Quick_sort(int a[], int l, int r){ if(l >= r) return ; int i = l - 1, j = r + 1, x = a[(l + r) / 2]; while(i < j){ do i++; while(a[i] < x); do j--; while(a[j] > x); if(i < j){ int t = a[i]; a[i] = a[j]; a[j] = t; } } Quick_sort(a, l, j), Quick_sort(a, j + 1, r); } int a[900007]; int main() { int n, k; scanf("%d%d", &n, &k); for(int i = 0; i < n; i++){ scanf("%d", &a[i]); } Quick_sort(a, 0, n - 1); printf("%d\n", a[k - 1]); return 0;//max }
