在一个数组中,要找第k小数 ,很多人的第一反应应该都是sort然后直接输出。但是昨天就被5e6卡了nlogn,这时候,stl里的一个函数就可以上场了:nth_element()

这个函数有四个参数:
1.first 容器开始位置
2.nth 要找的第k小(大)元素
3.last 容器结束位置
4.cmp 同sort,默认升序

该函数唯一能保证的就是第k小(大)元素在所选容器区间的第k个位置。不过拥有 O ( n ) O(n) O(n)的复杂度。

函数结束之后,在k位置之前的数都小于第k的元素,在k位置之后的数都大于第k的元素。但是不保证有序。

具体使用方式如下:

int main()
{
    int a[20] = {0, 1, 9, 4, 5, 2, 6, 8, 7, 3};
    int k = 2;
    nth_element(a + 1, a + k, a + 10);
    cout << "排序后:" << endl;
    for (int i = 1; i <= 9; i++)
        cout << a[i] << ' ';
    cout << endl;
    cout << a[k] << endl;
    return 0;
}
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐