acwing-786. 第k个数

本文最后更新于：2022年7月21日 下午

从小到大排序，取第k个数。

快速选择算法，非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;

const int N = 100000+10;

int n, k;
int q[N];

// 快速选择算法，非递归
int quick_sort(int q[], int l, int r, int k)
{
    if (l >= r) return q[l]; // 当[l,r]之间只剩一个元素，就是答案
    
    int  i = l - 1, j = r + 1, x = q[l + r >> 1];
    
    while (i < j)
    {
        do i++ ; while (q[i] < x); // 左边left 均 <= x
        do j-- ; while (q[j] > x); // 右边right 均 >= x
        
        if (i < j) swap(q[i], q[j]);
    }
    
    int sl = j - l + 1;
    if (k <= sl) return quick_sort(q, l, j, k);
    else return quick_sort(q, j + 1, r, k-sl);
    
}

int main()
{
    cin >> n >> k;
    
    for (int i = 0; i < n; i++) cin >> q[i];
    
    cout << quick_sort(q, 0, n-1, k) << endl;
    return 0;
}

快速选择算法，递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;

const int N = 100000+10;

int n, k;
int q[N];

// 快速选择算法，递归
int quick_sort(int q[], int l, int r, int k)
{
    while (true)
    {
        if (l >= r) return q[l]; // 当[l,r]之间只剩一个元素，就是答案
        
        int  i = l - 1, j = r + 1, x = q[l + r >> 1];
        
        while (i < j)
        {
            do i++ ; while (q[i] < x); // 左边left 均 <= x ， 从小到大排序
            do j-- ; while (q[j] > x); // 右边right 均 >= x
            
            if (i < j) swap(q[i], q[j]);
        }
        
        int sl = j - l + 1;
        if (k <= sl) 
            // return quick_sort(q, l, j, k);
            r = j;
        else 
            // return quick_sort(q, j + 1, r, k-sl);  
            k = k - sl,l = j + 1;
    }
}

int main()
{
    cin >> n >> k;
    
    for (int i = 0; i < n; i++) cin >> q[i];
    
    cout << quick_sort(q, 0, n-1, k) << endl;
    return 0;
}

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！