黑马程序员技术交流社区

标题: 求m个数据中前10小的数据 [打印本页]

作者: daoqin 时间: 2014-9-13 12:53
标题: 求m个数据中前10小的数据
本帖最后由 daoqin 于 2014-9-13 17:50 编辑

假定现在有m个数据，无序的（m<=100万），
请你编程实现找出m个数据中前10小的数据。时间限制：2000m （产生数据后开始计时，即数据已经在数组中了）例如：
输入
18代表18个数据
14 15 16 1 8 9 1 2 2 3 4 5 6 7 10 11 12 13
输出应该是：
1 1 2 2 3 4 5 6 7 8

作者: huanglyhf 时间: 2014-9-13 15:13
感觉来个快速排序，然后就结束了

作者: fantacyleo 时间: 2014-9-13 15:18
本帖最后由 fantacyleo 于 2014-9-13 15:21 编辑

楼主把题目再明确一点：如果有重复怎么算？比如1 1 1 2这种，输出时算4个数据还是2个数据？还有内存有无限制？如果没限制内存，我觉得楼上哥们儿的方法可行，我看过别人java自己写的快排代码，1000万无序数组也就2s

作者: daoqin 时间: 2014-9-13 17:33

fantacyleo 发表于 2014-9-13 15:18
楼主把题目再明确一点：如果有重复怎么算？比如1 1 1 2这种，输出时算4个数据还是2个数据？还有内存有无限 ...

你好，如果1122这种，应该输出4个。
这题我琢磨了半个，尝试各种解法，最后想到一个解法，临时队列。因为他只要最小的10个数据。
突然明白，这题如果要求你排序的话，就没意思了！
如果快排对于1000万无序数据可以2s完事，但是如果数据量再大一点任何排序算法是无法满足要求的。

作者: fantacyleo 时间: 2014-9-13 22:06

daoqin 发表于 2014-9-13 17:33
你好，如果1122这种，应该输出4个。
这题我琢磨了半个，尝试各种解法，最后想到一个解法，临时队列。因为 ...

不能说排序就没意思了。能在规定时间和内存限制之下解决问题的就是好算法。另外，这道题的时间复杂度下限是O(m)，因为至少要遍历每个数1次，快排思路仍有改进空间。我没有实际测试过，不过感觉O(m)的复杂度还是很容易做到的，因为10不随m变化，无论你怎么折腾那10个数，都是O(1)，比如你每取一个数n就用二分查找定位最小10个数中n的插入位置。当然constant factor会影响运行时间

作者: daoqin 时间: 2014-9-13 22:33

fantacyleo 发表于 2014-9-13 22:06
不能说排序就没意思了。能在规定时间和内存限制之下解决问题的就是好算法。另外，这道题的时间复杂度下限 ...

嗯嗯，有道理！

作者: fantacyleo 时间: 2014-9-13 23:59

fantacyleo 发表于 2014-9-13 22:06
不能说排序就没意思了。能在规定时间和内存限制之下解决问题的就是好算法。另外，这道题的时间复杂度下限 ...

按我这个思路测试了一下，m=1000000，平均20多毫秒

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2