【洛谷 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
分享
相关文章
|
11月前
|
【洛谷 P1923】【深基9.例4】求第 k 小的数 题解(快速排序)
该题目要求输入一组不超过5000000个奇数个整数,并找出其中第k小的数,不使用`nth_element`函数,而是通过实现快速排序来解决。样例输入为5个数1, 4, 3, 2, 5,k=1,输出第1小的数即最小值2。代码中定义了快速排序函数`quickSort`和划分函数`partition`,并使用`read`函数读取输入。在主函数中对数组进行排序后输出第k个元素。
128 0
|
11月前
|
【洛谷 P1464】Function 题解(递归+记忆化搜索)
该题目定义了一个递归函数w(a,b,c),具有特定的终止条件和递归规则。当a,b,c任一值小于等于0或大于20时,函数有特殊返回值。否则,根据a,b,c的相对大小关系应用不同的递归计算。给定输入是一系列的三元组(a,b,c),以1,1,1结束。程序使用记忆化搜索优化递归调用,避免重复计算。样例输入输出展示了如何计算w(1,1,1)w(2,2,2)
100 0
LeetCode - #53 最大子数组和(Top 100)
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
112 0
LeetCode - #15 三数之和(Top 100)
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
107 0
LeetCode - #46 全排列(Top 100)
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
153 0
LeetCode剑指 Offer 58—左旋转字符串(三次翻转/double+substr)
LeetCode剑指 Offer 58—左旋转字符串(三次翻转/double+substr)
104 0
LeetCode每日1题--三数之和
LeetCode每日1题--三数之和
103 0
LeetCode打卡 52八皇后Ⅱ&53最大子序和&54螺旋矩阵
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
154 0
LeetCode打卡 52八皇后Ⅱ&53最大子序和&54螺旋矩阵