区间第k大模版题目

Posted on In

题目大意:给定一个序列求这个序列的第k大数字,其中n属于1e7

我们显然可以直接sort一下,然后求解的话时间复杂度属于\(O(nlogn)\),貌似不太优秀

所以STL有个函数就叫:nth_element()

用法:nth_element(a + 1, a + k, a + 1 + n, cmp)

并且是\(O(n)\)的,也就不必快速排序来求了

考虑快排的思想,每次分治的时候,都选择一个基准值,然后看有多少个数字大于这个基准值即为cnt,然后根据k与cnt的关系把区间一分为2递归到自己需要的区间

期望分log次,\(n + n/2＋n/4...+1=O(n)\)

代码如下: 

1
2
3
4
5
6
7
main()
{
    nth_element(a + 1, a + k, a + 1 + n); 
    put(a[k]);
    return 0;
}

后记:

在这里,我谨代表所有被快速排序坑过的人们,向快排发明者致以最崇高的问候和衷心的祝愿