STL数组第k小数函数
在一个数组中,要找第k小数,很多人的第一反应应该都是sort然后直接输出。但是昨天就被5e6
卡了nlogn
,这时候,stl里的一个函数就可以上场了:nth_element()
这个函数有四个参数:
1.first 容器开始位置
2.nth 要找的第k小(大)元素
3.last 容器结束位置
4.cmp 同sort,默认升序
该函数唯一能保证的就是第k小(大)元素在所选容器区间的第k个位置。不过拥有$O(n)$的复杂度。
函数结束之后,在k位置之前的数都小于第k的元素,在k位置之后的数都大于第k的元素。但是不保证有序。
具体使用方式如下:
1 | int main() |