经典题-第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
" G1 ?' u1 I  C/ b3 N- z

-墟-

& }# L) M: w0 J; }
9 o! o6 @7 N4 b9 R. G% }有思路的大佬可以把代码发到评论区，明天发解析版の代码（我太懒了拖到明天）

黄蕊小白花

1. #include<iostream>
   
2. using namespace std;
   $ G4 `0 i( z" R
3. int main(){
   
4.     int n,k;
   4 b% ]7 ~' n8 k( `4 K' _, C
5.     cin>>n>>k;
   
6.     int a[n];
   ( O+ n0 ^8 I, i3 R$ \
7.     int b[k];
   ! ^8 L* o& Y' @; {& R1 v
8.     for(int i=0;i<k;i++){
   
9.         b[i]=5001;
   
10.     }
    ) i; A& G3 z0 x3 k% v9 g' {' k
11.     for(int i=0;i<n;i++){
    4 ?6 r; l( I: u& E
12.         cin>>a[i];
    # D) g2 Y3 ?; R8 a
13.     }
    
14.     int i=0;
    
15.     while(i<n){
    
16.         //cout<<i<<endl;
    ; v7 P) ?6 P! P* N  k. S
17.         for(int j=0;j<k;j++){
    
18.             if(b[j]>=a[i]){
    8 p" ?9 Y5 B0 v/ c1 }' E- q
19.     for(int p=k-1;p>j;p--){
    
20.                     b[p]=b[p-1];
    
21.                 }
    4 l$ ]) Y8 F- W: y/ W) r" A3 i9 G
22.                 b[j]=a[i];
    ' P6 U6 K, j; q6 }+ p
23.                 break;
    
24.        }
    
25. }
    
26. i+=1;
    
27.     }
    9 }4 ?8 W4 @) f0 v9 y2 R+ t) o# l
28.     cout<<b[k-1]<<endl;
    
29.     return 0;
    
30. }

复制代码

7 {, H2 G3 M/ c3 ]五星好评走一波～～～～～

7 u( b: v& Z* a& L

-墟-

实属惨烈

-墟-

2 D( r0 u& |2 b! K4 k) _* ]( h
  T, B3 }% \$ G! z7 k$ j- \这道题其实就是快速选择。看看n的大小，5000000，就算先sort一遍还是TLE，这个时候就应该从快排的角度去思考。每一次都会将k所在的位置的范围缩小，时间复杂度也是比快排还要低的（懒得估）。标准答案

1. #include <bits/stdc++.h>
   
2. using namespace std;
   9 K. Y) j; x) s
3. int n, k, a[5000001];
   7 o) q: {, |  r6 ?+ p
4. 
   
5. void read() { //快读，一定要用
   ( b4 r  k: u7 u. o3 [( Q
6.         char ch;
   
7.         ch = getchar();
   
8.         int f;
   
9.         for(int i = 0; i < n; i++) {
   
10.                 f = 1;
    % ~  j1 y  o5 k! O- _* D
11.                 while(ch < '0' || ch > '9') {
    
12.                         if(ch == '-')
    5 q/ c  U$ z$ }' I+ ^  ^- U# M- g
13.                                 f = -1;
    
14.                         ch = getchar();
    
15.                 }
    / R- p; l- w9 a9 G& y; j
16.                 while(ch >= '0' && ch <= '9') {
    
17.                         a[i] = a[i] * 10 + ch - '0';
    
18.                         ch = getchar();
    
19.                 }
    
20.                 a[i] *= f;
    ' g" D0 G; r2 }2 q, B# i* V, ~, k- i
21.         }
    
22. }
    " Y* S3 h# z6 `  b) u
23. 
    
24. int partition(int l, int r) { //用快排的方法，左边的永远大于右边的
    
25.         int pivot = a[l], left = l + 1, right = r;
      R- X' i/ H/ p% `; w9 Y/ @- _
26.         while(left <= right) {
    + k* Y  x$ e6 T& u! H
27.                 while(left <= right && a[left] <= pivot) {
    
28.                         left++;
    0 s4 n1 N- {7 e: g3 s
29.                 }
    : m5 |* W0 Y. L) X* y! y
30.                 while(left <= right && a[right] > pivot) {
    
31.                         right--;
    3 S: a' B: r* c
32.                 }
    
33.                 if(left < right) {
    
34.                         swap(a[left], a[right]);
    
35.                 }
    7 b' @/ e' k1 ]* e$ p( H
36.         }
    
37.         swap(a[l], a[right]);
    
38.         return right;
    " q" V5 t% j9 u) [
39. }
    
40. 
    & l( V+ b8 Q; \  V) o2 Q# _
41. int quickSelect(int l, int r, int k) { //如果第k个在左边就只在左边进行下一轮，在右边就在右边进行，正好是partition返回值则返回这个数
    
42.         if(l == r) {
    6 r8 `3 p- I# P7 ^
43.                 return a[l];
    2 G* B5 f: y, O7 _, k& l0 h1 X
44.         }
    ! ]0 h# u! n8 W  {
45.         int p = partition(l, r);
    3 ?1 b. `/ L0 e& K& a
46.         if(p == k - 1) {
    " E; ^9 E$ K* {
47.                 return a[p];
    1 E4 Y3 _% t. M# w+ Y+ A
48.         }else if(p < k - 1) {
    : y3 E$ @. F) G7 s# j+ J
49.                 return quickSelect(p + 1, r, k);
    4 \' R7 v& k7 R. l
50.         }else {
    
51.                 return quickSelect(l, p - 1, k);
    
52.         }
    
53. }
    ( N4 s! \! l  o+ [
54. 
    
55. int main() {
    $ u3 G+ y0 P# z5 t" [1 _
56.         scanf("%d%d", &n, &k);
    
57.         read();
    
58.         cout << quickSelect(0, n - 1, k);
    , q* `; S3 U7 m# J; [4 u2 v
59.         return 0;
    
60. }

复制代码

-墟-

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

7 H. W: O& ^/ r$ O2 W. G% ?20分，TLE了

黄蕊小白花

-墟- 发表于 2020-7-15 15:24
) d" `0 z  }3 I20分，TLE了

( ~% j0 Q% h, P. e" S20分是高是低

admin

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

" s$ _7 m( x' M1 w" r10个点，只过了2个，7个不过，不行哦
, w# {0 n/ ?+ z$ D3 b, x估计是超了时、过了内存或者不符合规定

Mozilla

9 |2 A+ D4 U1 |. P

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

, V7 p+ D$ c( T7 b# l, n+ z/ |写好了，并且优化了输出和速度。但是python由于要不停滴判断数据类型（还有其他原因），速度从根本上就比C++慢，所以对python的时限应该要放宽。

1. n=int(input('输入你的n'))
   " f- o1 d( C0 h8 U' \7 q1 r* i* N
2. k=int(input('输入你的k'))
   
3. 
   
4. num=[]
   
5. 
   3 w  n0 D3 ?4 u- b' D8 ]+ D
6. for i in range(n):
   
7.         num1=int(input('输入你的第%s个数'%n))
   9 b) T5 \2 ?/ U5 }
8.         n-=1
   
9.         num.append(num1)
   0 Z  S0 X) a  I: k1 i
10. 
    
11. 
    
12. def bubble(num2):
    
13.     for j in range(len(num2)-1):
    
14.                
    & B* r: K: m, g" `( V  t. X$ d
15.         for i in range(len(num2)-1):
    
16.             if num2[i]<num2[i+1]:
    ' M- p" e+ y% W4 M! a
17.                 num2[i+1],num2[i]=num2[i],num2[i+1]
    
18. 
    
19. 
    
20. 
    ! V" H! Y# r3 n. k2 Y: p$ a
21. bubble(num)
    
22. print(str(num[k-1]))
    5 G* T4 l( ?4 y; l- @( u4 x  U  k4 k

复制代码

admin

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

6 J5 r% x! v9 o% f5 c& [速度还得拿上去遛遛，才知道过不过