中位数问题分析 .doc
4星 · 超过85%的资源 需积分: 10 24 浏览量
2007-11-09
15:26:09
上传
评论
收藏 288KB DOC 举报 
一、 问题描述：
在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思
路即可。
（引自 csdn 论坛，网址：
http://topic.csdn.net/u/20071010/13/c97c22a5-12f4-4c02-8bac-3044bb3f3318.html）
二、 解决方法：
1. 扫描文件，确定各个长度的整数的个数。如果整数小于零，长度按负数
记。保存在哈希表 中， ：长度 ：个数。
2. 根据 1 求出整数的个数 。若 ，
则 中 位 数 的 位 置 ， 否 则 ， 中 位 数 由 位 置
和 对应的数（为描述方便暂称为‘确中数’）确定。以
下按照 的情况分析，如果 情况与 情况不同，
则在括号中说明。
3. 按照 值从小到大的顺序，执行
直到 ，此时的 值即为中位数的长度 。长度小于 的整数的
个 数 为 。 如 果 ， 扫 描 文 件 中 长 度 为
的整数即为所求中位数★①，否则继续以下步骤。
（如果 ，可根据 和 求出‘确中数’的长度 和
。如果 ，设 ，扫描文件中长度为 的
最 大 整 数 和 长 度 为 的 最 小 整 数 ，
即为所求中位数★②；否则
如果 ，扫描文件中长度为 的两个整数，求平均值即为所求中
位数★③，如果 继续以下步骤。）
4. 定义变量 。
5. 扫描文件中长度为 的整数。确定每个整数中第 位对
资源评论
oxygen2862012-09-09程序写的不错，不用再去搜概念了
