7-1 寻找第k小的数 (20 分)

深藏阁楼爱情的钟 2023-10-11 16:49 15阅读 0赞

7-1 寻找第k小的数 (20 分)

给定若干整数，请设计一个高效的算法，确定第k小的数。

#### 输入格式: ####

测试数据有多组，处理到文件尾。每组测试数据的第1行输入2个整数n，k（1≤k≤n≤1000000）。第2行输入n个整数，每个数据的取值范围在0到1000000之间。

#### 输出格式: ####

对于每组测试，输出第k小的数。

#### 输入样例: ####

5 3
    1 2 2 2 1
    9 3
    1 2 3 4 5 6 9 8 7

#### 输出样例: ####

2
    3

#### 提示: ####

如果提交后超时，请注意需要设计的是高效的算法！如果你初学《数据结构》，暂时设计不出来，请学完相关知识再回头来做。 也可以使用STL之sort、nth\_element函数求解。 另外，由于输入数据特别多，为减少输入数据的耗时，建议使用以下的输入外挂函数：

void scan_d(int &num)    
    {
            char in;
            in=getchar();
            while(in<'0'||in>'9') in=getchar(); 
            num=in-'0';
            while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}
    }

调用方法如下：

int n;
    scan_d(n);

算法分析：

这道题目没有必要用到给与的函数，第k小的数，只要输入的数据，进行排序后，我们只用输出第k个数即可。

代码实现：

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n,k;
        while (scanf("%d %d",&n,&k)!=EOF){
            int a[n];
            for(int i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            sort(a,a+n);
            cout<<a[k-1]<<endl;
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关 7-1 寻找第k小的数 (20 分)

7-1 寻找第k小的数 (20 分) 给定若干整数，请设计一个高效的算法，确定第k小的数。输入格式: 测试数据有多组，处理到文件尾。每组测试数据的第1行输入2个整数

深藏阁楼爱情的钟/ 2023年10月11日 16:49/ 0 赞/ 16 阅读

相关漫画：寻找无序数组的第k大元素

![format_png][] ![format_png 1][] ————— 第二天 ————— ![format_png 2][] ![format

淩亂°似流年/ 2023年07月12日 05:28/ 0 赞/ 12 阅读

相关寻找第k个最大数

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1: 输入: [3,2,1,5,

绝地灬酷狼/ 2023年06月19日 09:45/ 0 赞/ 16 阅读

相关寻找第 K 大的数

寻找第 K 大的数 1、参考资料 https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

爱被打了一巴掌/ 2022年12月05日 04:51/ 0 赞/ 220 阅读

相关寻找第k大or第k小的数--＞寻找中位数

> 快排思想，选取数组中第一个元素e为参考元素，利用partition() 使得数组左边的元素全都不大于e，数组右边的元素全都不小于e–>升序排序 > 设数组长度为n，若e的

Love The Way You Lie/ 2022年11月29日 11:27/ 0 赞/ 182 阅读

相关寻找第K大的数的方法总结

[寻找第K大的数的方法总结][K] 今天看算法分析是，看到一个这样的问题，就是在一堆数据中查找到第k个大的值。名称是：设计一组N个数，确定其中

客官°小女子只卖身不卖艺/ 2022年09月17日 15:18/ 0 赞/ 196 阅读

相关求前K小的数和第K小的数

求前K小的数和第K小的数 1. 前K小的数（堆排序实现） include<iostream> include<algorithm> inclu

落日映苍穹つ/ 2022年08月06日 13:19/ 0 赞/ 184 阅读

相关寻找最小的k个数

寻找最小的k个数 1. 题目描述在一个长度为n的数组中，寻找最小的k个数。（最大的k个数解法类似） 2. 排序法想法比较简

绝地灬酷狼/ 2022年08月05日 17:59/ 0 赞/ 188 阅读

相关分治法实验-寻找第k小元素

问题描述随机生成含有n个不同元素的数组L（n≥10000），要求找出第k小的元素（k≤n），完成下面的任务：（1）设计一个基于排序选择算法程序，编程调试正确（排序

梦里梦外;/ 2022年07月16日 00:18/ 0 赞/ 197 阅读

相关寻找第K大的数

1，对于一个有序数组则为第K个数，O（1） 2，对于一个无序数组使用修改的快排划分算法，时间复杂度为O（n） 3，对于两个无序数组

小咪咪/ 2022年05月21日 03:20/ 0 赞/ 190 阅读