当前位置:首页 > 排序 > 正文
SSOJ2054第k小数1
525+

题目大意:n个数,第k小的数在哪个位置?

【问题描述】

“哇,好多冰淇淋啊!”张琪曼跑到学院的冷饮店,伸出2根手指对冰淇淋老板说:“来3个。”老板蒙了,问:“几个?”张琪曼又伸出3根手指说:“2个。”

老板满头大汗:“我不管你要几个,只要你能从你口袋里的魔法石里找出第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)。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ2054第k小数1:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter