经典题-第k小的数

-墟-

题目描述

给定一个长度为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

-墟-

有思路的大佬可以把代码发到评论区，明天发解析版の代码（我太懒了拖到明天）

黄蕊小白花

1. #include<iostream>
   
2. using namespace std;
   
3. int main(){
   
4.     int n,k;
   
5.     cin>>n>>k;
   
6.     int a[n];
   
7.     int b[k];
   
8.     for(int i=0;i<k;i++){
   
9.         b[i]=5001;
   
10.     }
    
11.     for(int i=0;i<n;i++){
    
12.         cin>>a[i];
    
13.     }
    
14.     int i=0;
    
15.     while(i<n){
    
16.         //cout<<i<<endl;
    
17.         for(int j=0;j<k;j++){
    
18.             if(b[j]>=a[i]){
    
19.     for(int p=k-1;p>j;p--){
    
20.                     b[p]=b[p-1];
    
21.                 }
    
22.                 b[j]=a[i];
    
23.                 break;
    
24.        }
    
25. }
    
26. i+=1;
    
27.     }
    
28.     cout<<b[k-1]<<endl;
    
29.     return 0;
    
30. }

复制代码

五星好评走一波～～～～～

-墟-

实属惨烈

-墟-

这道题其实就是快速选择。看看n的大小，5000000，就算先sort一遍还是TLE，这个时候就应该从快排的角度去思考。每一次都会将k所在的位置的范围缩小，时间复杂度也是比快排还要低的（懒得估）。标准答案

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int n, k, a[5000001];
   
4. 
   
5. void read() { //快读，一定要用
   
6.         char ch;
   
7.         ch = getchar();
   
8.         int f;
   
9.         for(int i = 0; i < n; i++) {
   
10.                 f = 1;
    
11.                 while(ch < '0' || ch > '9') {
    
12.                         if(ch == '-')
    
13.                                 f = -1;
    
14.                         ch = getchar();
    
15.                 }
    
16.                 while(ch >= '0' && ch <= '9') {
    
17.                         a[i] = a[i] * 10 + ch - '0';
    
18.                         ch = getchar();
    
19.                 }
    
20.                 a[i] *= f;
    
21.         }
    
22. }
    
23. 
    
24. int partition(int l, int r) { //用快排的方法，左边的永远大于右边的
    
25.         int pivot = a[l], left = l + 1, right = r;
    
26.         while(left <= right) {
    
27.                 while(left <= right && a[left] <= pivot) {
    
28.                         left++;
    
29.                 }
    
30.                 while(left <= right && a[right] > pivot) {
    
31.                         right--;
    
32.                 }
    
33.                 if(left < right) {
    
34.                         swap(a[left], a[right]);
    
35.                 }
    
36.         }
    
37.         swap(a[l], a[right]);
    
38.         return right;
    
39. }
    
40. 
    
41. int quickSelect(int l, int r, int k) { //如果第k个在左边就只在左边进行下一轮，在右边就在右边进行，正好是partition返回值则返回这个数
    
42.         if(l == r) {
    
43.                 return a[l];
    
44.         }
    
45.         int p = partition(l, r);
    
46.         if(p == k - 1) {
    
47.                 return a[p];
    
48.         }else if(p < k - 1) {
    
49.                 return quickSelect(p + 1, r, k);
    
50.         }else {
    
51.                 return quickSelect(l, p - 1, k);
    
52.         }
    
53. }
    
54. 
    
55. int main() {
    
56.         scanf("%d%d", &n, &k);
    
57.         read();
    
58.         cout << quickSelect(0, n - 1, k);
    
59.         return 0;
    
60. }

复制代码

-墟-

黄蕊小白花 发表于 2020-7-15 11:29
五星好评走一波～～～～～

20分，TLE了

黄蕊小白花

-墟- 发表于 2020-7-15 15:24
20分，TLE了

20分是高是低

admin

黄蕊小白花 发表于 2020-7-15 18:36
20分是高是低

10个点，只过了2个，7个不过，不行哦
估计是超了时、过了内存或者不符合规定

Mozilla

-墟- 发表于 2020-7-13 15:14
有思路的大佬可以把代码发到评论区，明天发解析版の代码（我太懒了拖到明天） ...

写好了，并且优化了输出和速度。但是python由于要不停滴判断数据类型（还有其他原因），速度从根本上就比C++慢，所以对python的时限应该要放宽。

1. n=int(input('输入你的n'))
   
2. k=int(input('输入你的k'))
   
3. 
   
4. num=[]
   
5. 
   
6. for i in range(n):
   
7.         num1=int(input('输入你的第%s个数'%n))
   
8.         n-=1
   
9.         num.append(num1)
   
10. 
    
11. 
    
12. def bubble(num2):
    
13.     for j in range(len(num2)-1):
    
14.                
    
15.         for i in range(len(num2)-1):
    
16.             if num2[i]<num2[i+1]:
    
17.                 num2[i+1],num2[i]=num2[i],num2[i+1]
    
18. 
    
19. 
    
20. 
    
21. bubble(num)
    
22. print(str(num[k-1]))
    

复制代码

admin

Mozilla 发表于 2020-7-15 19:38
写好了，并且优化了输出和速度。但是python由于要不停滴判断数据类型（还有其他原因），速度从根本上就比C ...

速度还得拿上去遛遛，才知道过不过