经典题-第k小的数
本帖最后由 -墟- 于 2020-7-13 15:15 编辑题目描述给定一个长度为n（1≤n≤5000001）的无序正整数序列，以及另一个数k（1≤k≤n）（关于第k小的数：例如序列{1,2,3,4,5,6}中第3小的数是3。）输入第一行两个正整数n,k。第二行为n个正整数。输出第k小的数。样例输入6 3
1 2 3 4 5 6
样例输出
3
本帖最后由 -墟- 于 2020-7-13 15:16 编辑
有思路的大佬可以把代码发到评论区，明天发解析版の代码（我太懒了拖到明天） #include<iostream>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
int a;
int b;
for(int i=0;i<k;i++){
b=5001;
}
for(int i=0;i<n;i++){
cin>>a;
}
int i=0;
while(i<n){
//cout<<i<<endl;
for(int j=0;j<k;j++){
if(b>=a){
for(int p=k-1;p>j;p--){
b=b;
}
b=a;
break;
}
}
i+=1;
}
cout<<b<<endl;
return 0;
}
五星好评走一波～～～～～
实属惨烈 本帖最后由 -墟- 于 2020-7-15 15:22 编辑
这道题其实就是快速选择。看看n的大小，5000000，就算先sort一遍还是TLE，这个时候就应该从快排的角度去思考。每一次都会将k所在的位置的范围缩小，时间复杂度也是比快排还要低的（懒得估）。标准答案
#include <bits/stdc++.h>
using namespace std;
int n, k, a;
void read() { //快读，一定要用
char ch;
ch = getchar();
int f;
for(int i = 0; i < n; i++) {
f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
a = a * 10 + ch - '0';
ch = getchar();
}
a *= f;
}
}
int partition(int l, int r) { //用快排的方法，左边的永远大于右边的
int pivot = a, left = l + 1, right = r;
while(left <= right) {
while(left <= right && a <= pivot) {
left++;
}
while(left <= right && a > pivot) {
right--;
}
if(left < right) {
swap(a, a);
}
}
swap(a, a);
return right;
}
int quickSelect(int l, int r, int k) { //如果第k个在左边就只在左边进行下一轮，在右边就在右边进行，正好是partition返回值则返回这个数
if(l == r) {
return a;
}
int p = partition(l, r);
if(p == k - 1) {
return a;
}else if(p < k - 1) {
return quickSelect(p + 1, r, k);
}else {
return quickSelect(l, p - 1, k);
}
}
int main() {
scanf("%d%d", &n, &k);
read();
cout << quickSelect(0, n - 1, k);
return 0;
} 黄蕊小白花 发表于 2020-7-15 11:29
五星好评走一波～～～～～
20分，TLE了 -墟- 发表于 2020-7-15 15:24
20分，TLE了
20分是高是低 黄蕊小白花 发表于 2020-7-15 18:36
20分是高是低
10个点，只过了2个，7个不过，不行哦
估计是超了时、过了内存或者不符合规定 本帖最后由 Mozilla 于 2020-7-15 19:41 编辑
-墟- 发表于 2020-7-13 15:14
有思路的大佬可以把代码发到评论区，明天发解析版の代码（我太懒了拖到明天） ...
写好了，并且优化了输出和速度。但是python由于要不停滴判断数据类型（还有其他原因），速度从根本上就比C++慢，所以对python的时限应该要放宽。
n=int(input('输入你的n'))
k=int(input('输入你的k'))
num=[]
for i in range(n):
num1=int(input('输入你的第%s个数'%n))
n-=1
num.append(num1)
def bubble(num2):
for j in range(len(num2)-1):
for i in range(len(num2)-1):
if num2<num2:
num2,num2=num2,num2
bubble(num)
print(str(num))
Mozilla 发表于 2020-7-15 19:38
写好了，并且优化了输出和速度。但是python由于要不停滴判断数据类型（还有其他原因），速度从根本上就比C ...
速度还得拿上去遛遛，才知道过不过