题解 P1138 【第k小整数】

~~贡献分掉了来水题解.jpg~~ 我们知道，有一个与快排相似的“快速次序选择”算法。 大概流程如下： 以某个数为中间点将序列分为两半 检查中间点的排名 若大于k，对左半区间递归 小于k，对右半区间递归 --- 很简单对不对？ 复杂度显然$O(n)$，最坏$O(n^2)$ 实现也不难，跟平衡树的kth差不多 --- 然而STL帮你写好了（ `std::nth_element(first,nth,last)`函数，帮你把`[first,last)`中的元素分为小于/大于等于nth的两部分（ 然后nth位置上就是正确答案了（ --- ```cpp #include<cstdio> #include<algorithm> int n,k,tot,a[10005]; bool vis[30005]; int main() { scanf("%d%d",&n,&k); while(n--) { int x; scanf("%d",&x); if(!vis[x]) { a[tot++]=x; vis[x]=1; } } if(k>tot) { puts("NO RESULT"); return 0; } std::nth_element(a,a+k-1,a+tot); printf("%d",a[k-1]); } ``` 注意STL左闭右开，所以排名从0开始（