【洛谷 P1923】【深基9.例4】求第 k 小的数 题解(快速排序)

简介: 该题目要求输入一组不超过5000000个奇数个整数,并找出其中第k小的数,不使用`nth_element`函数,而是通过实现快速排序来解决。样例输入为5个数1, 4, 3, 2, 5,k=1,输出第1小的数即最小值2。代码中定义了快速排序函数`quickSort`和划分函数`partition`,并使用`read`函数读取输入。在主函数中对数组进行排序后输出第k个元素。

【深基9.例4】求第 k 小的数

题目描述

输入 $n$($1 \le n < 5000000$ 且 $n$ 为奇数)个数字 $a_i$($1 \le a_i < {10}^9$),输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题,因为本题的重点在于练习分治算法。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2

思路

先快速排序,然后通过数组索引访问第k小的数。由于数据过大,需要打开O2优化。

AC代码

#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

const int maxn = 5000005;
int a[maxn];

void read(int &x)
{
   
    char ch;
    x = 0;
    while (('0' > ch || '9' < ch))
    {
   
        ch = getchar();
    }
    while (!('0' > ch || '9' < ch))
    {
   
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}

int *particition(int a[], int *low, int *high)
{
   
    int *l = low, *r = high, pivot = *low;
    while (l < r)
    {
   
        while (l < r && *r > pivot)
        {
   
            r--;
        }
        while (l < r && *l <= pivot)
        {
   
            l++;
        }
        if (l < r)
        {
   
            swap(*(l++), *(r--));
        }
    }
    if (*l > pivot)
    {
   
        swap(*(l - 1), *low);
        return l - 1;
    }
    else
    {
   
        swap(*l, *low);
        return l;
    }
}

void quickSort(int a[], int *low, int *high)
{
   
    if (low < high)
    {
   
        int *mid = particition(a, low, high);
        quickSort(a, low, mid - 1);
        quickSort(a, mid + 1, high);
    }
}

int main()
{
   
    int n, k;
    read(n);
    read(k);
    for (int i = 0; i < n; i++)
    {
   
        read(a[i]);
    }
    quickSort(a, a, a + n - 1);
    /* for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    } */
    cout << a[k] << endl;
    return 0;
}
目录
相关文章
|
开发框架 数据库 数据安全/隐私保护
FastAdmin框架实现数据表的增删改查
FastAdmin框架实现数据表的增删改查
966 0
|
C++
【洛谷 P1923】【深基9.例4】求第 k 小的数 题解(nth_element)
该题目要求输入一个奇数个整数 $n$($1 \le n &lt; 5000000$)和一个位置 $k$,在给定的 $n$ 个不超过 ${10}^9$ 的整数中找出第 $k$ 小的数。样例输入为 `5 1` 和 `4 3 2 1 5`,输出第 $1$ 小的数,即 `2`。解决方案使用 C++ 的 `nth_element` 函数来找到第 $k$ 小的数。
152 0
|
存储 Java 数据库
基于springboot的医院信息管理系统(程序+代码+文档)
基于springboot的医院信息管理系统(程序+代码+文档)
|
12月前
|
IDE Java 编译器
Java“找不到符号” 错误怎么查找解决
“找不到符号”是Java编程中常见的编译错误,通常表明代码试图访问未声明或不可见的符号(如类、方法或变量)。解决此问题需检查拼写、导入包是否正确及作用域是否合适。确保使用正确的类路径和库,可有效避免此类错误。若问题依旧,查阅官方文档或使用调试工具定位错误亦为良策。
5728 10
|
存储 人工智能 C++
【PTA】L1-064 估值一亿的AI核心代码(详C++)
【PTA】L1-064 估值一亿的AI核心代码(详C++)
357 1
|
缓存 Java 应用服务中间件
【Tomcat】史上最全下载、安装配置及使用教程,(2022最新..建议收藏,教学)附Tomcat常见报错解决方法
【Tomcat】史上最全下载、安装配置及使用教程,(2022最新..建议收藏,教学)附Tomcat常见报错解决方法
5449 1
【Tomcat】史上最全下载、安装配置及使用教程,(2022最新..建议收藏,教学)附Tomcat常见报错解决方法
|
SQL 大数据 调度
大数据线上问题排查系列 - HIVE 踩坑记- hive.metastore.dml.events
大数据线上问题排查系列 - HIVE 踩坑记- hive.metastore.dml.events
|
存储 C语言
顺序栈和链栈的定义和使用C语言实现(附有完整代码)
顺序栈和链栈的定义和使用C语言实现(附有完整代码)
648 0
|
设计模式 资源调度 JavaScript
Ant Design Pro安装及简单搭建
Ant Design Pro安装及简单搭建
792 1
|
存储 前端开发 NoSQL
【毕业设计之python系列】基于Flask的在线学习笔记的设计与实现
【毕业设计之python系列】基于Flask的在线学习笔记的设计与实现
1328 2