分治与归并计数 · HTML
数学 / 逻辑形态
目标为升序零基 target。partition(lo,hi) 后 pivot 位于 p，左侧 <= pivot、右侧 > pivot。p=target 返回；否则永久排除不含 target 的一侧。
识别信号
- 只求第 k 大/小、中位数或一个排名边界。
- 输入可随机访问并允许原地重排。
- 不需要前 k 项有序。
- 希望避免完整 O(n log n) 排序。
- 可接受随机 pivot 的期望界。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 在线数据流 | 未来项会改变排名，应用有界堆或双堆。 |
| 严格最坏界 | 普通 Quickselect 最坏 O(n²)；需要堆或确定性 pivot。 |
| 需要稳定全序 | partition 改写顺序且不稳定；完整排序更合适。 |
核心不变量
目标秩始终在当前闭区间 [lo,hi]；每次 partition 后 pivot 的秩位置已确定，不含 target 的一侧可永久丢弃。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 可变数组、lo/hi、零基 target 和随机 pivot。 |
| Transition | partition 得 p；p<target 则 lo=p+1，p>target 则 hi=p-1，否则返回。 |
| Frontier / order | 唯一仍可能包含目标秩的连续区间；与 Quicksort 不同，不处理另一侧。 |
Python 骨架
from random import randrange
def kth_smallest(nums, k):
if not 1 <= k <= len(nums): raise ValueError('k')
a, target = list(nums), k - 1
lo, hi = 0, len(a) - 1
while lo <= hi:
q = randrange(lo, hi + 1)
a[q], a[hi] = a[hi], a[q]
pivot, p = a[hi], lo
for i in range(lo, hi):
if a[i] <= pivot:
a[p], a[i] = a[i], a[p]; p += 1
a[p], a[hi] = a[hi], a[p]
if p == target: return a[p]
if p < target: lo = p + 1
else: hi = p - 1
正确性思路
- partition 后 p 左侧均 <= pivot、右侧均 > pivot，pivot 的一个最终秩为 p。
- target<p 时目标不在 p 及右侧；target>p 对称。
- 区间严格缩小且从不排除 target，命中时返回正确。
复杂度
| Time | Space | Parameters |
|---|
| 随机 pivot 期望 O(n)，最坏 O(n²) | 原地迭代 O(1)；示例复制输入 O(n) | n 为元素数，k 为 1-based；重复值影响平衡。 |
边界条件
- k 越界
- 空数组
- 大量重复
- 有序/逆序输入
- 是否允许改输入
- 第 k 大的 target 换算
错误模式
| Pattern | Why it fails / fix |
|---|
| k 下标错位 | 第 k 小 target=k-1；第 k 大 target=n-k。 |
| partition 契约与边界不一致 | 先固定 [lo,hi]、等号去向和 pivot 最终位置。 |
| 像 Quicksort 搜两侧 | 只保留含 target 的一侧，否则失去选择优势。 |
| 固定恶劣 pivot | 有序输入可 O(n²)；用随机化或更稳健选点。 |
选择与排除规则
- 静态一次秩查询且允许改序：Quickselect。
- 在线或需稳定最坏界：堆/排序。
- 先统一成升序零基 target。
- 重复极多时考虑三路 partition。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 下一轮定位 4，无需完整排序。 |
| Setup | 读数 [8,2,6,4]，求第 2 小。 |
| Trace | pivot=6 后 p=2；target=1，只保留左侧 [2,4]。 |
Recall prompts
我的补充