n个球与n个杯子的期望nlogn配对算法设计求助

核心思路：借助快速排序的分治思想，用杯子作为"标尺"间接划分球的重量区间 #

不需要直接比较两个球的重量，而是利用杯子的测试反馈完成分治，具体步骤如下：

1. 选择分治基准

   • 从当前未配对的杯子集合中任选一个杯子作为基准杯C。

2. 用基准杯划分球集合

   • 将所有未配对的球依次放入C中测试，根据反馈分成三组：
     • 匹配组：仅包含与C重量匹配的球（直接完成该杯与球的配对）
     • 过重组：放入C时提示"过重"的球（这些球的重量 > C的目标重量，对应杯子必然是比C目标重量大的杯子）
     • 过轻组：放入C时提示"过轻"的球（这些球的重量 < C的目标重量，对应杯子是比C目标重量小的杯子）

3. 同步划分杯子集合

   • 将当前未配对的杯子（除基准杯C）按目标重量分为两组：
     • 重杯子组：目标重量大于C的杯子（对应过重组的球）
     • 轻杯子组：目标重量小于C的杯子（对应过轻组的球）

4. 递归处理子问题

   • 对（过轻组球，轻杯子组）和（过重组球，重杯子组）分别重复上述步骤，直到所有球与杯子完成配对。

时间复杂度说明 #

和快速排序的期望复杂度逻辑一致：每次基准杯能将问题近似拆分为两个规模减半的子问题，每层递归需要O(k)的测试次数（k为当前未配对的球/杯数量），期望递归深度为O(logn)，因此整体期望时间复杂度为O(nlogn)。

内容的提问来源于stack exchange，提问作者Ray