<-制作不易,如果满意就点一下吧
P1923.求第 k 小的数
题目描述
输入 $n$($1 \le n < 5000000$ 且 $n$ 为奇数)个数字 $a_i$($1 \le a_i < {10}^9$),输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。
请尽量不要使用 $nth_element$ 来写本题,因为本题的重点在于练习分治算法。
输入格式
无
输出格式
无
样例 #1
样例输入 #1
5 1
4 3 2 1 5
样例输出 #1
2
方法一:
题目不让我用
$nth_element$
我就偏要用(不过 STL 常数普遍较大……但还是能过此题)
重点(敲黑板):
它的用法是 $nth_element(a+x,a+x+y,a+x+len);$
执行之后数组 $a$ 下标 $x$ 到 $x + y - 1$ 的元素都小于 $a[x + y] $。下标 $ x + y + 1$ 到 $x + len - 1$ 的元素都大于 $ a[x + y]$ ,但不保证数组有序。此时 $ a[x + y] $ 就是数组区间 $x$ 到 $x+len-1$ 中第 $ y $ 小的数,当然也可以自己定义 $ cmp $ 函数。
$code$:
#include<bits/stdc++.h>
using namespace std;
int x[5000005], k;
int main(){
int n;
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i ++) scanf("%d", &x[i]);
nth_element(x, x + k, x + n);
printf("%d", x[k]);
return 0;
}
方法二:
对原数组进行快速排序,然后 $O(1)$ 输出。
$code$:
#include<bits/stdc++.h>
using namespace std;
int x[5000005], k;
int main(){
int n;
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i ++) scanf("%d", &x[i]);
sort(x, x + n);
printf("%d", x[k]);
return 0;
}
方法三:
根据快排思想来寻找第 $k$ 小的数。
快排的核心思想是二分。
在原二分的基础上可以进行修改:因为每次递归都会将数组划分为三部分,
而答案只会在这三部分中的一个,不需要再对其他部分进行搜索,
从而达到优化时间复杂度的效果。
$code$:
#include<bits/stdc++.h>
using namespace std;
int x[5000005], k;
void qsort(int l, int r){
int i = l, j = r, mid = x[(l+r)/2];
do{
while(x[j] > mid) j--;
while(x[i] < mid) i++;
if(i <= j){
swap(x[i], x[j]);
i ++, j --;
}
}while(i <= j);
if(k <= j) qsort(l, j);
else if(i <= k) qsort(i, r);
else{
printf("%d", x[j+1]);
exit(0);
}
}
int main(){
int n;
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++) scanf("%d", &x[i]);
qsort(0, n - 1);
return 0;
}