经典题-第k小的数

-墟-

! E& U& ?7 e1 s# o) |7 V$ C# W2 D
题目描述

给定一个长度为n（1≤n≤5000001）的无序正整数序列，以及另一个数k（1≤k≤n）（关于第k小的数：例如序列{1,2,3,4,5,6}中第3小的数是3。）

输入

第一行两个正整数n,k。

第二行为n个正整数。

输出

第k小的数。

样例输入6 3
6 }5 I. T1 I, F( A  _/ J1 2 3 4 5 6
样例输出
- ~) C3 H" |5 j/ |% [3

-墟-

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

黄蕊小白花

1. #include<iostream>
   : j. _/ u& g3 ^; p2 j8 [- C
2. using namespace std;
   
3. int main(){
   * C3 t1 I) i& |: {$ e7 H$ P
4.     int n,k;
   ) f2 a3 ?0 i+ s
5.     cin>>n>>k;
   
6.     int a[n];
   
7.     int b[k];
   * F( E- I9 m& u" K' Z. S
8.     for(int i=0;i<k;i++){
   - }5 J9 F/ I2 m" ]/ a
9.         b[i]=5001;
   ! s/ J9 B- d0 f* ?
10.     }
    $ S: y( y* c8 ]/ f) p" L' l/ T
11.     for(int i=0;i<n;i++){
    
12.         cin>>a[i];
    1 ^5 U. }7 I5 H1 I
13.     }
    , {4 r" q  q: s1 ~* X) g$ l  Q: ~
14.     int i=0;
    
15.     while(i<n){
    9 x+ `' ~: H' R5 w$ I6 H0 \
16.         //cout<<i<<endl;
    % ?, O# l+ ^$ v* P2 H% x. Q6 }
17.         for(int j=0;j<k;j++){
    ) F" Q; q7 F$ j8 d0 y7 x& Q
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;
    ( W4 n' d2 D0 s. E5 x1 @
24.        }
    5 h: M0 c) {( h2 H, E' D+ t
25. }
    
26. i+=1;
    
27.     }
    . E+ q4 |0 S( o" i1 t, d
28.     cout<<b[k-1]<<endl;
    6 j0 C! w1 p1 L; }
29.     return 0;
    
30. }

复制代码

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

-墟-

实属惨烈

-墟-

0 k2 k% W) V5 X5 S3 k- @* W
这道题其实就是快速选择。看看n的大小，5000000，就算先sort一遍还是TLE，这个时候就应该从快排的角度去思考。每一次都会将k所在的位置的范围缩小，时间复杂度也是比快排还要低的（懒得估）。标准答案
( x$ _8 i: ]5 z

1. #include <bits/stdc++.h>
   
2. using namespace std;
   . R6 T3 V% h+ h" S" x
3. int n, k, a[5000001];
   & [- S" C4 ^7 \
4. 
   
5. void read() { //快读，一定要用
   ) A  }2 C5 }1 n  f& i
6.         char ch;
   
7.         ch = getchar();
   - _) h  [- B4 `- `" q# z3 t
8.         int f;
   2 I9 g5 a( L: W; B  d$ ^: a& t1 M
9.         for(int i = 0; i < n; i++) {
   
10.                 f = 1;
    ! d7 V- p) g# q; u' K& ?
11.                 while(ch < '0' || ch > '9') {
    * H2 ]& C9 {7 Q% ?
12.                         if(ch == '-')
    8 C* _' f. n% z, y7 {9 ^
13.                                 f = -1;
    " ?# [7 n" S+ Q4 J) z1 S
14.                         ch = getchar();
    % m$ n$ @% d, N9 j
15.                 }
    & O% L# |% A7 E: ?+ {( y1 G
16.                 while(ch >= '0' && ch <= '9') {
    
17.                         a[i] = a[i] * 10 + ch - '0';
    
18.                         ch = getchar();
    3 N8 f& [4 ^- A; M3 g/ x
19.                 }
    
20.                 a[i] *= f;
    
21.         }
      d( j0 C& g% o* U
22. }
    
23. 
    
24. int partition(int l, int r) { //用快排的方法，左边的永远大于右边的
    
25.         int pivot = a[l], left = l + 1, right = r;
    , t  A$ ?7 O2 E3 S% r4 L# m
26.         while(left <= right) {
    5 o6 `! p# a* g
27.                 while(left <= right && a[left] <= pivot) {
    2 z' _2 C2 O' ?; j
28.                         left++;
    
29.                 }
    3 }! S' ~1 ~; g5 j) v- q3 A
30.                 while(left <= right && a[right] > pivot) {
    
31.                         right--;
    
32.                 }
    : U0 H) g1 B. Y) C) {( r4 e' _
33.                 if(left < right) {
    % |% ]9 S6 p- F3 G0 r
34.                         swap(a[left], a[right]);
    : `: X1 C  u7 c/ @0 [# y
35.                 }
    
36.         }
    ( t& G% |: N2 |. [6 M( l
37.         swap(a[l], a[right]);
      N) [% T$ n0 _" H% W- I1 ]+ F
38.         return right;
    
39. }
    1 j* N0 W+ w' Z" o: `3 T
40. 
    % P+ y- s. p6 E( W* u
41. int quickSelect(int l, int r, int k) { //如果第k个在左边就只在左边进行下一轮，在右边就在右边进行，正好是partition返回值则返回这个数
    
42.         if(l == r) {
    6 w- g4 Q+ d; U) r
43.                 return a[l];
    
44.         }
    
45.         int p = partition(l, r);
    
46.         if(p == k - 1) {
    
47.                 return a[p];
    ) i; z$ q0 q' z
48.         }else if(p < k - 1) {
    
49.                 return quickSelect(p + 1, r, k);
    
50.         }else {
    ! s: t1 P6 i( H9 b$ n
51.                 return quickSelect(l, p - 1, k);
    - u# i$ B. D8 w
52.         }
    * u" Y- H9 E+ i9 U  Q9 X+ R
53. }
    
54. 
    - g$ K8 O5 ^# k7 O7 b3 X1 C+ R
55. int main() {
    ! c; L7 R, G& T+ O! L( [- E4 T
56.         scanf("%d%d", &n, &k);
    4 l3 o* C9 ~" N% P% ^5 d1 m% r0 m4 w
57.         read();
    9 K- t" R4 `/ Y7 g: r0 i/ o
58.         cout << quickSelect(0, n - 1, k);
    
59.         return 0;
    8 f1 L6 }) ^2 w: y& ]$ }9 g, d+ p
60. }

复制代码

-墟-

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

  ~. }. X' n4 {' Y& W  {20分，TLE了

黄蕊小白花

-墟- 发表于 2020-7-15 15:24
  s1 J8 _* M. n6 f20分，TLE了

20分是高是低

admin

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

0 |% i  n( W: z! r10个点，只过了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. 
   ; F" _. B" z: b& v9 L& z/ ~7 Q* t
6. for i in range(n):
   
7.         num1=int(input('输入你的第%s个数'%n))
   
8.         n-=1
   
9.         num.append(num1)
   - n; s6 @( c3 @1 }
10. 
    2 x1 Z; a) p+ L& v/ H- \8 T
11. 
    
12. def bubble(num2):
    , ^7 k+ d4 ^! Q( {0 G% }. B
13.     for j in range(len(num2)-1):
    
14.                
    & h, b5 k' r. a! l! A1 v' E+ R
15.         for i in range(len(num2)-1):
    $ b  M  _% d1 ?9 x! W# N
16.             if num2[i]<num2[i+1]:
    ' r( [9 x1 z/ K% N
17.                 num2[i+1],num2[i]=num2[i],num2[i+1]
    " I0 Q+ h3 z8 T
18. 
    % T* o2 e* a* }, D4 v5 z% s
19. 
    
20. 
    + L2 u9 S5 ~  K" [: F0 ?* y7 O; G7 @
21. bubble(num)
    
22. print(str(num[k-1]))
    

复制代码

admin

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

, q& e- t/ b( \. b: B* v, H7 i8 I速度还得拿上去遛遛，才知道过不过