文档章节

查找第K大的数

o
 osc_n6euf5h6
发布于 2019/03/19 23:28
字数 239
阅读 6
收藏 0

精选30+云产品,助力企业轻松上云!>>>

类快排 第一种方法 o(n)

2019.06.08更正错误

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;

int s[N];

int partion(int l,int r) {
    int tmp = s[l];
    int i = l, j = r;
    while(i < j) {
        while(i < j && s[j] >= tmp) j--;
        while(i < j && s[i] <= tmp) i++;
        if(i < j) {
            swap(s[i], s[j]);
        }
    }
    // now i == j
    swap(s[i], s[l]);
    return i;
}


void selectKth(int l,int r,int k) {
    if(l > r)
        return ;
    int c = partion(l,r);
    if(c == k)
        return ;
    else if(c < k)
        selectKth(c+1,r,k);
    else
        selectKth(l,c,k);
}

int main()
{
    srand(time(NULL));
    int n = 10;
    int m = 10;

    for(int i=1; i<=n; i++)
        s[i] = rand() % 15;
    int k = 5;
    selectKth(1,n,k);
    printf("%d\n", s[k]);
    sort(s+1,s+11);
    printf("%d\n", s[k]);

    return 0;
}

第二种方法 用到堆了

大根堆 是arr[i] <= arr[2i+1] && arr[i] <= arr[2i], 因此大根堆的堆顶是最小值,所以排序的话呢,就是从小到大排的...

priority_queue<int> que;
int k = 5;
for(int i=1; i<=n; i++) {
    que.push(s[i]);
    if(que.size() > k) {
        que.pop();
    }
}
cout<<que.top()<<endl;   
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

格式编号始终显示2个小数位 - Format number to always show 2 decimal places

问题: I would like to format my numbers to always display 2 decimal places, rounding where applicable. 我想将数字格式化为始终显示2个小数位,并在适用的情况下四舍五入。 Examples...

富含淀粉
56分钟前
22
0
Docker可视化工具Portainer

1 前言 从没想到Docker也有可视化的工具,因为它的命令还是非常清晰简单的。无聊搜了一下,原来已经有很多Docker可视化工具了。如DockerUI、Shipyard、Rancher、Portainer等。查看对比了一番...

南瓜慢说
58分钟前
20
0
日志系统新贵 Loki,真香!!

最近,在对公司容器云的日志方案进行设计的时候,发现主流的ELK或者EFK比较重,再加上现阶段对于ES复杂的搜索功能很多都用不上最终选择了Grafana开源的Loki日志系统,下面介绍下Loki的背景。...

庞陆阳
今天
14
0
jQuery获取select onChange的值 - jQuery get value of select onChange

问题: I was under the impression that I could get the value of a select input by doing this $(this).val(); 我的印象是我可以通过执行$(this).val();来获取选择输入的值$(this).val()......

javail
今天
13
0
道翰天琼解密宇宙信息大脑三者最核心奥秘,破解认知智能基础理论(群聊形式)

三体论是探索研究宇宙,信息和人类大脑三者关系的理论体系。是认知智能的奠基理论体系之一。宇宙和信息,信息和人类大脑,人类大脑和宇宙,三者之间存在着某种未被完全揭示的奥秘。三体论的核...

jackli2020
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部