SSOJ2054第k小数1
2555+
作者：crxis 发布：2017-09-30 分类：排序
题目大意：n个数，第k小的数在哪个位置？
【问题描述】
“哇，好多冰淇淋啊！”张琪曼跑到学院的冷饮店，伸出２根手指对冰淇淋老板说：“来３个。”老板蒙了，问：“几个？”张琪曼又伸出３根手指说：“２个。”
老板满头大汗：“我不管你要几个，只要你能从你口袋里的魔法石里找出第k小的魔法石，冰淇淋随便你吃。”
现在你知道该怎么做了吧？那就是：对于给定的n个元素的无序数组，要求从中找出第k小的元素。
【输入格式】
第一行是总数n（1<n<100000）和k，第二行是n个待比较元素。
【输出格式】
第k小的数在数组中的位置。
【输入样例】
5 3
25 9 90 57 3
【输出样例】
1
解题思路
将n个数从小到大排序后，输出a[k]即那个数是多少，如何输出它原来的位置呢？可以考虑用结构体，记录该数的值的同时，记录该数的编号，最后输出d[k].i。这样时间复杂度是排序的复杂度。然而，排序后，我们只用到其中的一个数而已，并不需要全部排序，如何降低时间复杂度呢？就是在使用快排的时候，如果左半部分没有第k小就只看右半部分，如果右半部分没有也只看左半部分，这样时间复杂度是n+n/2+n/4+n/8+…+n/n < 2n，即O(n)。
程序实现
