数值不等于记录
假设有限数组有 个记录,每个记录都有来自全序集合的键值及不同身份。我们要选出键值最小的恰好 个记录,其中 。键值可以重复。任务未必要求输出已排序。所选键值的多重集唯一,但若平局没有规则,所选身份未必唯一。我们约定边界平局时优先选原始位置较早的记录,并按原输入次序输出所选记录。
当 ,返回空列表。当 ,按输入次序返回所有记录。对 ,令 是由一开始计算、按重数排列的第 小键值。把记录分为键值小于、等于及大于 的三组,分别称为 。由排名定义,
定义 4.2.1
(带最早位置平局规则的最小 k 选取)
设键值按重数排序为 。若恰好 个记录所成集合 的键值多重集等于 ,就称 为最小 选取;等价地, 中每个键值都不大于 以外的每个键值。在所有最小 选取中,最早位置选取是指其中来自 的记录在输入中位置最早的那一个,并按输入次序返回。
因此每个有效答案必须包含所有 、排除所有 ,并从 恰好选 个记录。把所有键值不大于 的记录都取出,可能取出太多。边界规则按原位置选取 中最早的 个记录。
反例模式
保留所有不大于阈值的键值
断言:要取最小的 个记录,只需求出 ,再保留所有键值不大于 的记录。取键值 及 。排序后为 ,所以 ,而每个键值都不大于 :此规则保留全部五个记录,而不是三个。这里 的键值是 ,所以 ,三个键值为 的记录中只可保留 个。修正后的规则保留位置 的记录,按输入次序键值为 。边界上的平局,正是阈值过滤与计数结果不一致之处。
观察边界
例题 4.2.2
(有重复键值的列表中的第 4 小值)
对列表 的第 小值,选首项 为枢轴。较小、相等、较大部分分别是 、、。由于 ,答案是 ,无需再分割。核对:排序后为 ,第四项是 。
在默认追踪中,、、。组件展示可重现的固定首项枢轴选择追踪,并非随机算法,也不选取记录身份。若七个记录按输入次序命名为 ,按我们的平局规则所选身份为 :三个小于 的键值,以及最早等于 的记录。返回 保持输入次序,但没有按键值排序。组件上方的段落在静态阅读时提供键值分割。
例题 4.2.3
(三个边界记录中选两个,并保持输入次序)
取键值 ,位置为 ,。排序后为 ,所以 、(键值 )、(位置 )。键值 的配额是 。第二次扫描:位置 (键值 ,已用配额 )输出;位置 (键值 )跳过;位置 (键值 ,已用配额 )输出;位置 因配额用完、位置 因键值大于 而跳过;位置 (键值 )输出。结果是位置 ,键值为 。第三个键值为 的记录被舍弃,尽管它的键值等于 。
例题 4.2.4
(退化情形:k = 0、k = n 及全部键值相等)
时,任何输入的答案都是空列表,不需要阈值。 时,按输入次序返回所有记录。若键值为 而 ,则 、、、,配额为 :第二次扫描输出位置 和 ,之后不再输出。不等式 成立,正如排名定义所保证。当 时,同一扫描返回全部四个记录,与 的规则一致。
为何构造正确
先用任何正确的排名选择程序求 。扫描原数组一次以计算 ,再扫描一次:输出每个键值小于 的记录,并只输出最早的 个键值等于 的记录;忽略大于 的键值。它由左至右读取原位置,故输出保持输入次序,而相等键值的身份选择是确定的。
定理 4.2.5
(两次扫描给出最早位置选取)
设 ,,。两次扫描的程序恰好输出 个记录,按输入次序排列,且输出集合就是最早位置的最小 选取。此外,每个最小 选取都包含 的全部记录、不含 的任何记录,并恰好含 中的 个记录。
证明
(计算键值个数并迫出边界分组)
排名不等式 给出 ,所以边界记录的配额可以填满,第二次扫描输出 个记录。排序后的键值中恰有 个小于 ,即 ;而 全部等于 ,因为它们不大于 又不小于 。输出的键值是 的 个键值加上 个 ,其多重集是 ,所以输出集合是最小 选取。
再设 为任意最小 选取,即 中每个键值都不大于 以外的每个键值。若有 在 之外,则 中每个键值都不大于 的键值,而它小于 ;于是 ,得 ,与 矛盾。若有 在 之内,则 以外每个键值都不小于 的键值,而它大于 。但 有 个记录, 只剩 个位置可容纳它们,所以 中必有一个键值不大于 的记录在 之外,矛盾。因此 是 加上 中的 个记录;最早位置规则选 中最早的 个,正是扫描所输出的。
证明透视
排名不等式与平局规则用在哪里
计数步骤只用到小于 的键值个数 及 这个事实,从不查看哪个记录带哪个键值,所以求 可用任何正确的排名程序。 的左半使配额 至少为一,即确实需要一个边界记录;右半使配额可以达成。若误把 取成 ,不等式可能不成立,扫描便可能输出错误个数的记录。最早位置规则与键值多重集无关,它只在键值相等的记录之间作选择,使输出被唯一确定。
组件展示一种求 的方法。三路分割时,设目前由一开始计算的局部排名为 :若 ,保留较小部分;若 ,在相等部分停止;否则保留较大部分,并把 改为 。排名调整针对目前子问题。组件的特定追踪在相等部分停止;单靠其选择结果不会保留或选出记录身份。
成本、修改输入及流式替代法
若排名程序使用 次键值比较,两次额外扫描使用 次比较。总成本继承所用程序的最坏情况或期望保证。若该程序会修改输入,应在键值的私人副本上执行,使第二次扫描仍按原始次序看见记录。键值副本需要 个额外键值槽,另有 个输出记录;选择程序可能需要更多工作空间。另一种设计是在修改前为记录保存原始索引,按 选最小的 个配对,然后以 次比较排序所选索引,恢复输入次序。按配对选取才能落实位置最早的平局规则。
概念视角结构
把键值与位置配对,使所有键值互异
把每条记录换成配对 ,按字典序比较。这些配对全都互异,所以排名为 的配对 是真正的门槛,而位置最早的选择恰是配对不超过 的那些记录。对键值 及 ,排序后的配对以 开头,故 ,所选位置为 。
固定首项枢轴的快速选择可能需要 次比较。适当的均匀随机枢轴及三路分割,在所述模型下有期望线性的选择界;它不是每次执行的最坏情况界,组件也没有模拟随机性。若输出还须按键值排序,使用比较排序需额外 次比较。
对 的数据流,另一种契约是保留至多 个记录的最大堆,按 字典序排列。键值全序及互异索引令这些配对形成全序。每次输入后,它包含最小的 个配对:若堆未满,插入新配对;若堆已满且新配对不小于最大值,丢弃新配对;若堆已满且新配对较小,替换最大值并恢复堆次序。归纳法可证不变量。此法使用 次比较,存储 个记录。堆次序不是输出次序;若要按原始索引返回,还需另行排序。 时不存储任何记录。
常见错误
(在重排后的数组上做第二次扫描)
设记录 的键值为 ,。则 、,最早位置选取是 ,按 返回。若排名程序已把数组重排为 ,而第二次扫描读取的就是这个数组,它会输出 ,然后输出遇到的第一个 ,即 。身份错了,次序也不是输入次序。应扫描原始记录,或保留了原位置的副本。
常见错误
(键值相等时仍替换堆的最大值)
在流式版本中取 ,三个键值同为 的记录依次以索引 到达。堆中有 与 。新到的 按字典序大于最大值 ,所以被丢弃。若键值不大于最大值(含相等)就替换,便会保留较迟的记录而丢掉较早的,违反最早位置规则。
习题
快速检查
(键值为 ,各记录按输入次序有不同身份,且 。求 、、,及按上述平局规则选出的原位置。)
先把键值按重数排序,再读出第四项。
解答 · 答案
排序后键值为 ,所以 、、。选位置 :所有小于 的键值,加上最早的 ,按原次序返回。
快速检查
(若平局跨越边界,为何返回所有键值不大于 的记录是错的?)
数一数返回的记录个数,再与 比较。
解答 · 答案
对上一题的键值,这会返回全部六个记录而非四个;三个边界相等记录中只需一个。
快速检查
(若排名选择重排了输入的唯一副本,但输出必须按原次序排列,会有什么额外问题?)
想一想第二次扫描读取的是什么。
解答 · 答案
选择过程可能破坏原次序。应保存未改动的输入副本,或保留原始索引并明确恢复所需次序;只知道所选键值不足以恢复记录身份。