C****t
发帖数: 2 | 1 给定存有一个整数组的 binary file，数组长度不定。设计一个程序读取这个文件，找
出这个数组中最大的K个元素并排序，同是记录这个数组最后的K个元素。要求首先考虑
内存优化，其次运算速度。
我的做法是首先从文件中读取K个元素，如果数组长度不大于K,则直接排序。否则先找
出这个数组中最小的元素，然后从文件中读取下一个元素，比较后替换最小值。依次进
行直到文件结束，然后再统一排序。同时把数组的最后K个元素存在一个QUEUE里。
不确认是不是最优解法，欢迎大家讨论。 | d****n
发帖数: 12461 | 2 use a K min heap比用你的k array效率更好。 | s**x
发帖数: 7506 | 3 K 很小， 应该是标准的 min heap with K elements, nlogK.
K 很大， 但内存放得下， selection sort, O(n)
内存放不下， 挺麻烦。
你没提到 heap, 10 分 给你 3 分吧。 | C****t
发帖数: 2 | 4 不是码工职位，内存有限，复杂的数据结构和算法或许不能满足要求？
【在 s**x 的大作中提到】
: K 很小， 应该是标准的 min heap with K elements, nlogK.
: K 很大， 但内存放得下， selection sort, O(n)
: 内存放不下， 挺麻烦。
: 你没提到 heap, 10 分 给你 3 分吧。
| w*****d
发帖数: 105 | 5 k个数能放内存的话，heap+deque；
放不了内存，则遍历多次，还是heap+deque，每次得到N个最大和N个最后（假设N个能
放内存），共需要k/N趟。 |
|
