《算法第四版》课后练习题1.1.34答案

习题：1.1.34

过滤。以下哪些任务需要（在数组中，比如）保存标准输入中的所有值？（答案中用A表示）

哪些可以被实现为一个过滤器且仅使用固定数量的变量和固定大小的数组（和N无关）？（答案中用B表示）

在每个问题中，输人都来自于标准输入且含有个0到1的实数。

• 打印出最大和最小的数
• 打印出所有数的中位数
• 打印出第k小的数，k小于100
• 打印出所有数的平方和
• 打印出N个数的平均值
• 打印出大于平均值的数的百分比
• 将N个数按照升序打印
• 将N个数按照随机顺序打印

要点分析

一.  白名单过滤（课本第29页）

如果可能，我们的测试用例都会通过模拟实际情况来展示当前算法的必要性。这里该过程被称为白名单过滤。具体来说，可以想象一家信用卡公司，它需要检查客户的交易账号是否有效。为此，它需要：

• 将客户的账号保存在一个文件中，我们称它为白名单
• 从标准输人中得到每笔交易的账号；
• 使用这个测试用例在标腓输出中打印所有与任何客户无关的账号，公司很可能拒绝此类交易。

在一家有上百万客户的大公司中，需要处理数百万甚至更多的交易都是很正常的。为了模拟这

种情况，我们在本书的网站上提供了文件largew.txt（100万个整数）和IargeT.txt（10m万个整数），该数据的下载请查看看本站：如何学习算法和数据结构?一文中提供了相关的下载地址。

二.  中位数

中位数又称中值，英语：Median

统计学中的专有名词，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。

对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。[1]

参考答案

• 打印出最大和最小的数 ：B
• 打印出所有数的中位数：A
• 打印出第k小的数，k小于100：B
• 打印出所有数的平方和：B
• 打印出N个数的平均值：B
• 打印出大于平均值的数的百分比：A
• 将N个数按照升序打印：A
• 将N个数按照随机顺序打印：A

参考资料

[1] 百度百科：中位数