AcWing 786. 第k个数 *

[toc]

AcWing 786. 第k个数 - 糖豆爸爸 - 博客园

AcWing 786. 第k个数【简单】*

一、题目描述

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。

输出格式
输出一个整数，表示数列的第 k 小数。

数据范围
1≤n≤100000,
1≤k≤n

输入样例：

5 3
2 4 1 5 3

输出样例：

3

二、AC代码

$fileName

version 1.0 模板

这是我一开始写的，肯定是能过的，没想那么多，总结交了——直到我看了题解。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;
int q[N];
void quick_sort(int q[], int l, int r);

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    printf("%d\n", q[k - 1]);
    
    return 0;
}

void quick_sort(int q[], int l, int r){
    if (l >= r) return;
    
    int i = l - 1, j = r + 1, x = q[l + (r- l) / 2];
    while (i < j){
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

version 2.0 y总

$fileName
y总讲解 
// y总
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;
int q[N];
int quick_sort(int q[], int l, int r, int k);

int main(void)
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    printf("%d\n", quick_sort(q, 0, n - 1, k)); // 这里传入的是 k
    
    return 0;
}

int quick_sort(int q[], int l, int r, int k){
    if (l >= r) return q[l];
    
    int i = l - 1, j = r + 1, x = q[l + (r - l) / 2];
    while (i < j){
        do i++; while (q[i] < x);
        do j--; while (q[j] > 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);    // 右侧
}

version 3.0 y总改良版

缩小范围的递归判断条件可以更简洁一些，直接判断下标即可。

// tonngw
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;
int n, k;
int q[N];

// 改为 int
int quick_sort(int l, int r, int k);

int main(void)
{
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    // 返回的就是第 k 大的数，注意这里传入的是下标 k - 1
    printf("%d\n", quick_sort(0, n - 1, k - 1));
    
    return 0;
}

int quick_sort(int l, int r, int k){
    // 如果找到了则直接返回
    if (l >= r) return q[l];
    
    int i = l - 1, j = r + 1, x = q[l + (r - l) / 2];
    while (i < j){
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    // 如果第 k 大的数在左半边，则递归左半边寻找
    if (k <= j) return quick_sort(l, j, k);
    // 否则递归右半边
    return quick_sort(j + 1, r, k);
}

三、错误分析

暂且不表，先不深入探究，老是刨根问底太浪费时间了······

1. 为什么y总的main函数里传过来的是 k 而不是 k - 1？

$fileName
“学长”答疑

printf("%d\n", quick_sort(q, 0, n - 1, k));

评论区里写法不太一样，用的是下标，所以是 k - 1。

2. 为什么评论区的写法更好？

tonngw：缩小范围的递归判断条件可以更简洁一些，直接判断下标即可。

3. 一些相关帖子

  1. AcWing 786. 保证 [l, j-1] <= pivot, [j+1, r] >= pivot, 同时[j] == pivot 的解法 - AcWing
  2. AcWing 785. 快速排序算法的证明与边界分析 - AcWing

四、总结

我：嗯，确实是简单题，基本上跟上一道模板题一模一样。
好像忘了看题解······

卧槽！是我头脑简单了。

  1. 这是快速排序模板的练习题。
  2. 不一样的地方在于它可以利用快排模板，但却不需要真的把所有数据排序完成，每次一分为二后，只关心自己所有的那一半，就是可以节约一半的递归时间。
  3. 由于是关心 位置（第几个），所以在递归时需要携带这个参数。
  4. 位置这个参数 不是一成不变的，因为如果在左侧，那么就是原来的位置，如果在右侧，那就需要减去整个左侧的长度。这个 k 参数可以理解为 在当前数组中的位置，最终将确定这个位置上的值。
  5. 最后，直接使用 q[k] 就是拿到了最终这个位置上应该存在的值。