在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。
我想了一下,这个思路不知道正不正确,怕自己想漏了
思路是:
例如,有数字 1,1,2,2,3,3,4,5,6
现在按照 1~2 3~4 5~6 分为三段,那么第一段n1的数字个数是4, n2为3, n3为2, 中位数是第5个,
在n2中第 5 - n1 = 2 个数, 也就是3, 如果数字总个数是偶数 取第 size/2 和 size/2+1的数字的平均值就好了
那么思路就是将整数从0~最大值分段;
记录每段的数字个数 为p1 p2.... pn;
中位数所在的段 Pm; 则中位数是第10G/2-(P1 + P2 + ... Pm-1) 个, 若该段的数字比较少了就直接读文件取出在该段范围中的数字排序即可
若该段数字还是比较多,针对Pm的分段起点和终点再次分段,重复这个过程
感觉按照这个办法内存很少就够了 为了效果好一点可以分段分细一点,内存绰绰有余
大家觉得有没有什么问题?

没有，常规操作。
不过实现起来会有这样那样的情况

如果不要求效率的话，可以强行把文件模拟成数组，进行 quick select 。

没看懂，如果是要求中位数，那么你的方法既然记录了数字个数pn，那么不如用树状数组求和，二分比较，复杂度o（log^2n）。

用文件的形式创建二分查找树， （指针用类似静态链表的方法实现），从源文件一个一个读一个一个写到结果。主要考虑瓶颈会在磁盘IO上，毕竟HHD随机存取很慢，SSD也不过几十MB/S，几个G文件还是很慢的。

我有个问题，这些数的范围？小于1e7的话应该好办