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

简介: 该题目要求输入一个奇数个整数 n1n<5000000)和一个位置 k,在给定的 n 个不超过 109 的整数中找出第 k 小的数。样例输入为 `5 1` 和 `4 3 2 1 5`,输出第 1 小的数,即 `2`。解决方案使用 C++ 的 `nth_element` 函数来找到第 k 小的数。

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

题目描述

输入 n1n<5000000n 为奇数)个数字 ai1ai<109),输出这些数字的第 k 小的数。最小的数是第 0 小。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5
AI 代码解读

样例输出 #1

2
AI 代码解读

思路

用nth_element求第 k 小的数。

AC代码

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

vector<int> v;

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 main()
{
   
    int n, k;
    read(n);
    read(k);
    for (int i = 0; i < n; i++)
    {
   
        int in;
        read(in);
        v.push_back(in);
    }
    nth_element(v.begin(), v.begin() + k, v.end());
    cout << v[k] << endl;
    return 0;
}
AI 代码解读
HEX9CF
+关注
目录
打赏
0
0
0
0
1
分享
相关文章
【面试必刷TOP101】反转链表 & 链表内指定区间反转
【面试必刷TOP101】反转链表 & 链表内指定区间反转
107 0
|
11月前
|
【洛谷 P1923】【深基9.例4】求第 k 小的数 题解(快速排序)
该题目要求输入一组不超过5000000个奇数个整数,并找出其中第k小的数,不使用`nth_element`函数,而是通过实现快速排序来解决。样例输入为5个数1, 4, 3, 2, 5,k=1,输出第1小的数即最小值2。代码中定义了快速排序函数`quickSort`和划分函数`partition`,并使用`read`函数读取输入。在主函数中对数组进行排序后输出第k个元素。
134 0
[leetcode ~dp ]279. 完全平方数
[leetcode ~dp ]279. 完全平方数
LeetCode - #46 全排列(Top 100)
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
163 0
LeetCode - #15 三数之和(Top 100)
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
117 0
LeetCode - #53 最大子数组和(Top 100)
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
118 0
LeetCode - #22 括号生成(Top 100)
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
【PAT甲级 - C++题解】1048 Find Coins
【PAT甲级 - C++题解】1048 Find Coins
73 0
【PAT甲级 - C++题解】1068 Find More Coins
【PAT甲级 - C++题解】1068 Find More Coins
118 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等