深海中的STL—nth_element

如果让你求区间第k大,你会怎么做呢?

主席树?确实是个不错的选择(不过像我这种垃圾还是乖乖打暴力吧) 在c++的stl库中,提供了nth_element这样一个函数

它的用法是nth_element(a+l,a+k,a+r)

这样它会使a这个数组中区间(l,r)内的第k大的元素处在第k个位置上(相对位置)

但是它并不保证其他元素有序! 不过根据网友的实验,貌似在vs上是有序的,不过在dev中是无序的

时间复杂度:O(n)

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    static int a[15]={0,1,2,5,7,3,4,1};
    for(int i=1;i<=8;i++) printf("%d ",a[i]);printf("\n");
    nth_element(a,a+4,a+8);
    for(int i=1;i<=8;i++) printf("%d ",a[i]);printf("\n");
    
    return 0;
} 

输出结果

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

讨厌算法的程序员 1 | 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生出一...

3017
来自专栏架构之路

寻找第K元素的八大算法、源码及拓展

一、问题描述  所谓“第(前)k大数问题”指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第(前)k个数的问题。 第K大问题可以是现实问题,譬如竞价...

5576
来自专栏python读书笔记

《python算法教程》Day3 - 递归递归简介代码示例

这是《python算法教程》的第3篇读书笔记。由于之前看书的效率太低了,所以拖了一个多星期才写第三篇读书笔记。这次主要简单总结一下递归(recursion)。 ...

3058
来自专栏Leetcode名企之路

【Leetcode】60. 第k个排列

给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1:

3172
来自专栏Hongten

算法与数据结构(一)

  用计算机实现问题求解,实质上就是在计算机中建立一个解决问题的模型。用来表示问题或处理问题的模型可以有不同的抽象形式:

922
来自专栏前端说吧

JS-用js的for循环实现九九乘法表以及其他算数题等

5186
来自专栏数据结构与算法

小米OJ刷题日志

$f[i][j]$表示第一个队列匹配到了$i$位置,第二个队列匹配到了$j$位置是否可行

5232
来自专栏xcywt

《大话数据结构》一些基础知识

第一章 数据结构绪论 1.4 基本概念和术语 1.4.1 数据 数据:描述客观事物的符号,是计算机中可以操作的对象,是能被极端及识别,并输入给计算机处理的符号集...

3569
来自专栏java一日一条

最快最简单的排序算法:桶排序

在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总...

1081
来自专栏Android机动车

数据结构学习笔记——总述

数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。

691

扫码关注云+社区

领取腾讯云代金券