假定现在有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

感觉来个快速排序，然后就结束了

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

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

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

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

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

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

嗯嗯，有道理！

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

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