题目
只有2G内存的pc机，在一个存有10G个整数的文件，从中找到中位数，写一个算法。
思路一：外排序（排序-归并）
思路二：堆排序（转换为求前5G大的元素）
思路三：分而治之：基于二进制位映射分割
思路四：基数排序（计数排序）
思路五：桶排序
思路六：bitmap位图算法
参考：https://zhuanlan.zhihu.com/p/75397875
1.利用外排序的方法，进行排序 ,然后再去找中位数
2.另外还有个思路利用堆
先求第1G大，然后利用该元素求第2G大，然后利用第2G大，求第3G大...当然这样的话虽不需排序，但是磁盘操作会比较多，具体还需要分析下与外排序的效率哪个的磁盘IO会比较多
建立一个1g个整数的最大值堆，如果元素小于最大值则入堆，这样可以得到第1g大的那个元素然后利用这个元素，重新建一次堆，这次入堆的条件还要加上大于这个第1g大的元素，这样建完堆可以得到第2g大的那个 ...
3.借鉴基数排序思想
偶认为可以用位来判断计数，从最高位到最低位，为了方便表述我们假设为无符号整数，即0x00000000~0xFFFFFFFF依次递增，那么可以遍历所有数据，并记录最高位为0和1的个数（最高位为0的肯定是小于最高位为1的）记为N0、N1
那么根据N0和N1的大小就可以知道中位数的最高位是0还是1
假设N0>N1，那么再计算N00和N01，
如果N00>(N01+N1)，则说明中位数的最高两位是00
再计算N000和N001.。。。依次计算就能找到中位数
如果改进一下，设定多个计数器
好像一次磁盘io也可以统计出N0,N00,....的数值
4.借鉴桶排序思想
一个整数假设是32位无符号数
第一次扫描把0~2^32-1分成2^16个区间，记录每个区间的整数数目
找出中位数具体所在区间65536*i~65536*(i+1)-1
第二次扫描则可找出具体中位数数值
第一次扫描已经找出中位数具体所在区间65536*i~65536*(i+1)-1
然后第二次扫描再统计在该区间内每个数出现的次数，就可以了
网友评论