STL数组第k小数函数
在一个数组中,要找第k小数,很多人的第一反应应该都是sort然后直接输出。但是昨天就被5e6卡了nlogn,这时候,stl里的一个函数就可以上场了:nth_element()这个函数有四个参数:1.first 容器开始位置2.nth 要找的第k小(大)元素3.last 容器结束位置4.cmp 同sort,默认升序该函数唯一能保证的就是第k小(大)元素在所选容器区间的第k个位置。不过拥有O(n)O(
·
在一个数组中,要找第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;
}
更多推荐
已为社区贡献4条内容
所有评论(0)