题目大意:n个数,第k小的数在哪个位置?
"哇,好多冰淇淋啊!"张琪曼跑到学院的冷饮店,伸出2根手指对冰淇淋老板说:"来3个."老板蒙了,问:"几个?"张琪曼又伸出3根手指说:"2个."
老板满头大汗:"我不管你要几个,只要你能从你口袋里的魔法石里找出第k小的魔法石,冰淇淋随便你吃."
现在你知道该怎么做了吧?那就是:对于给定的n个元素的无序数组,要求从中找出第k小的元素.
第一行是总数n(1<n<100000)和k,第二行是n个待比较元素.
第k小的数在数组中的位置.
将n个数从小到大排序后,输出a[k]即那个数是多少,如何输出它原来的位置呢?可以考虑用结构体,记录该数的值的同时,记录该数的编号,最后输出d[k].i.这样时间复杂度是排序的复杂度.然而,排序后,我们只用到其中的一个数而已,并不需要全部排序,如何降低时间复杂度呢?就是在使用快排的时候,如果左半部分没有第k小就只看右半部分,如果右半部分没有也只看左半部分,这样时间复杂度是n+n/2+n/4+n/8+...+n/n < 2n,即O(n).
SSOJ2054第k小数1:等您坐沙发呢!