首页 > 其他分享 >第k个数【模板题】

第k个数【模板题】

时间:2023-01-05 14:45:03浏览次数:25  
标签:下标 int 个数 整数 element nth 模板

第k个数

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

输入格式
第一行包含两个整数 \(n\) 和 \(k\)。

第二行包含 \(n\) 个整数(所有整数均在 \(1∼109\) 范围内),表示整数数列。

输出格式
输出一个整数,表示数列的第 \(k\) 小数。

数据范围
\(1≤n≤100000,\)
\(1≤k≤n\)
输入样例:
5 3
2 4 1 5 3
输出样例:
3

Code

点击查看代码
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int quick_select(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 >> 1];
    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 (sl >= k) return quick_select(q, l, j, k);	//第k小的数
	//选择性递归一边(如果左边的数的个数大于k,那么k就在l和j之间)
    else return quick_select(q, j + 1, r, k - sl);	//第k - sl小的数
	//否则k就在j+1和r之间
}

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

nth_element(STL)

1. 头文件algorithm

void nth_element (Iterator first, Iterator first+nth, Iterator last, Compare comp);

2. 求区间第k小

举个栗子求第3小,对于 a[9]={4,7,6,9,1,8,2,3,5};

nth_element(a,a+2,a+9),将下标为2,也就是第3个数放在正确的位置,求的是第3小的数a[2]。(下标从零开始

nth_element(a,a+k,a+n),函数只是把下标为k的元素放在了正确位置,对其它元素并没有排序,当然k左边元素都小于等于它,右边元素都大于等于它,所以可以利用这个函数快速定位某个元素

3. 求第k大

我们可以转化成求第n-k+1小,此时下标应该是n - k

nth_element(a,a+n-k,a+n),将下标为n-k,也就是第n-k+1个数放在正确的位置,求的是第k大的数a[n-k]。

当然也可以把要处理的序列全变成负值,那样求得第k小就是第k大了。

标签:下标,int,个数,整数,element,nth,模板
From: https://www.cnblogs.com/J-12045/p/17027479.html

相关文章

  • h5代码模板
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="utf-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><metaname="......
  • php发送钉钉消息,模板例子
    <?php#key与secret私钥$appkey="ding6prlu53np9e6ly0vv2";$appsecret="KW9_HiBHyLs5YYgb0zfHd3uAvtrbbMZy5bv5eEsQzzctA9nbZjk6KuEMudJFWllVeI";//请求token$u......
  • 模板引擎:第三章:使用Freemark做企业级SEO推广
    为什么做SEO?当公司项目已接近尾声时,这个时候就需要推广了,这个时候就需要SEO了,那SEO是什么呢?seo中文翻译是搜索引擎优化。它利用搜索引擎的规则提高网站在有关搜索引擎内......
  • 7-3 统计一行文本的单词个数 (15 point(s))
    本题目要求编写程序统计一行字符中单词的个数。所谓“单词”是指连续不含空格的字符串,各单词之间用空格分隔,空格数可以是多个。输入格式:输入给出一行字符。输出格式:在一......
  • 比较四个数的大小
    源码分享#include<stdio.h>#include<stdlib.h>intmain(){inta,b,c,d,max;scanf("%d%d%d%d",&a,&b,&c,&d);if(a>b)max=a;elsemax=b;if(max<c)max=c;if(m......
  • 比较三个数的大小
    1、方法一2、方法二3、方法二的优缺点1、方法一先比较a和b,将较大值赋值给max再比较max和c,若c>max,把c赋值给max最后输出max#include<stdio.h>#include<stdlib.h>intmain(){......
  • Python算法题头部与模板
    头部importsys;readline=sys.stdin.readlineread=lambda:[int(x)forxinreadline().split()]alloc=lambda*s:len(s)!=1and[alloc(*s[1:])foriinr......
  • 从键盘输入两个正整数,让计算机判断第2个数是不是第1个数的约数。如果是则输出yes,不是
    1、约数概念2、源码分享3、知识点1、约数概念约数,又称因数,整数a除以整数b(b≠0)除得的商正好是整数而没有余数,我们就说a能被b整除,或b能整除a。a称为b的倍数,b称为a的约数。2、......
  • 【C++】以最快的速度求一个数的因数之和
    源代码: #include<iostream>usingnamespacestd;intmain(){inta,b=0;cin>>a;for(inti=2;i<a;i++){if(a%i==0){b+=i;......
  • 可视化Echart模板component
    <template><divclass="com-container">地区销售排行图表<divclass="com-chart"ref="rank_ref"></div></div></template><script>exportdefau......