CSCI3160 Special 1：选择与加权中位数

原件：Sp01 题目（本地课件） p.1。原文件标题将课程号写作 CSCI3610，官网目录为 CSCI3160，保留这项来源差异。 结构：每题先给题解，再给具体解析。全部解法为独立推导，Special 官网没有官方答案。

Problem 1：常数时间实现取模

题解

对正整数 x,y，先求整数商 $q=\lfloor x/y\rfloor$，返回 $r=x-qy$。在课程 RAM 模型提供常数时间除法（或除法加取整）、乘法与减法，且数在字长内时，总时间 O(1)。

具体解析

由 q 的定义，$q\le x/y<q+1$；乘正数 y 并减 qy，得到 $0\le x-qy<y$，且 x=qy+r，所以 r 就是除法余数。自取 x=17,y=5，q=3，返回17−15=2；x<y 时 q=0，返回 x；整除时返回0。

必须说清计算模型。若仅允许加减而不提供除法，不能不加证明地把“除一下”当 O(1)；若是任意精度整数，时间还取决于位数。本题依赖课堂的字长 RAM 原子操作约定。

Problem 2：一次选择后的子数组规模

题解

枢轴34的秩为6；目标 k=10 在较大侧。子数组含6个元素 [58,98,83,45,85,91]，接下来找其中第4小。

具体解析

小于34的是23、32、24、18、2，共5个，加枢轴自身得到秩6。它左边5个和自身都小于目标，删去这6个后，原来第10小变成右边第10−6=4小。右边规模12−6=6。算法不需要把原数组排序，仅一次扫描分组计数即可。

本题问的是子问题数组大小6，不能把新的 k=4 当答案。原数组排序为2、18、23、24、32、34、45、58、83、85、91、98，第10小85确实是右边第4小。

Problem 3：用线性最坏中位数黑盒实现线性最坏选择

题解

n=1直接返回。其他情况调用黑盒得到题目定义的第 floor(n/2) 小元素 m，线性划分、计算其秩 r；若k=r返回，k<r进入左侧，否则进入右侧并把目标秩改为k−r。每次只进入一侧，最坏时间 O(n)。

具体解析

题面的中位数用下取整；n=1会给第0小，所以必须先处理单元素基例。对n≥2，最大子数组规模至多 ceil(n/2)，黑盒与划分合计 cn 工作。沿递归链的工作上界是 $cn+c\lceil n/2\rceil+c\lceil n/4\rceil+\cdots=O(n)$，取整额外项至多O(log n)，不会改变线性界。

若允许重复值，应分成小于、等于、大于三组：当k落在等值组秩范围就返回，否则按删掉的总数改秩。中位数两侧的严格组仍至多约一半。本题集合语境下元素互异，等值组只有枢轴。

自取n=8、k=7，中位数秩4，进入最多4个数的右侧找第3小；规模链至多8、4、2、1。与随机选择不同，这里每一步都有确定的平衡保证，所以是最坏线性而非仅期望线性。

Problem 4：输出指定秩区间的全部元素

题解

在线性期望时间分别选择原集合第k₁小的值a和第k₂小的值b，再扫描原集合，输出所有满足a≤x≤b的元素。总期望O(n)，输出不要求排序。

具体解析

互异性保证数值顺序与秩一一对应：低于a的秩小于k₁，高于b的秩大于k₂，中间恰有k₂−k₁+1个值。两次随机选择的时间期望分别O(n)，线性期望可相加，不要求两次耗时独立。

选择算法可能原地修改输入，可在副本上运行，或保留全部元素后扫描当前排列；无论排列如何，值不会改变。自取[8,1,6,3,9]、秩2到4：边界a=3、b=8，扫描原序可输出8、6、3，答案集合正确。若额外要求升序输出，一般还要处理排序成本，不能把题目没要求的输出顺序悄悄加上。

Problem 5：数值同时作为权重的加权中位数

题解

总重量W为所有正整数之和。所求是按数值排序后，累计和第一次达到或超过W/2的那个元素。无需真的排序：用选择式划分，同时计算较小组重量L。设当前目标重量H初始为W/2：

选择枢轴v并分成小于v的组、v、大于v的组
L ← 小于组的数值和
若 H ≤ L：在小于组继续，H不变
否则若 H ≤ L+v：返回v
否则：H ← H-L-v，在大于组继续

每轮用均匀随机枢轴，期望O(n)；或用Q3中位数枢轴得到最坏O(n)。

具体解析

排序后的前缀和严格上升，因为所有元素正。必有唯一一个位置从小于H跨到至少H：它左边总和严格小于H，右边总和为W减包含自己的前缀，不超过H，正好满足原题两种不等号。

进入右组时，左组和枢轴已永久计入“累计前缀”，所以目标阈值要减去它们；进入左组时，还没跳过任何重量，H不变。若H恰等于L，应进入左组，不能返回v，否则v左侧恰为W/2，违反严格小于。

原理演算（自取）：S={1,2,3,6}，W=12、H=6。若枢轴3，L=3，L+3=6，返回3；左和1+2=3<6，右和6≤6。若错误要求右和也严格小于6，就会排除正确解。

时间按元素个数分析，不按数值重量：每轮求和、划分O(当前个数)，随机秩决定的规模缩小与Quickselect相同；重量集中在一个很大数上不会使每轮扫描更多元素。输入字长内的求和须可表示，或另行计大整数位复杂度。

把重量阈值随递归一起带走。 仍用 $\{1,2,3,6\}$，初始 $H=6$。假设先取枢轴 2，左侧重量 $L=1$，加枢轴后为 3；由于 $6>3$，递归到 $\{3,6\}$，目标重量变成 $H'=6-3=3$。再取枢轴 3，左侧重量 0，而 $0<3\le3$，返回 3。它在原集合左边重量 $1+2=3<6$，右边重量 $6\le6$，满足原题两侧的不对称条件。子问题阈值不一定是子问题总重量的一半：这里剩余重量 9，而阈值是 3；重新取 $9/2$ 会改变问题。

来源与证据

本组题面p.1，题解为独立推导；数值例子为本文自取，Q2采用原题数据。未将自行题解标作官方答案。