知识卡片
快速选择维护相对子区间的秩
在闭区间 [left,right] 寻找第 k 小,k 从1开始。分区返回 p 后,中枢相对秩为 p−left+1;若目标更小则保留 k 并搜索左区间,若更大则搜索右区间并令 k 减去该相对秩。函数返回的是数组索引,不是元素值。
这个换算在 left 不为零时不可省略。调用者应保证区间有效且 1≤k≤right−left+1;示例代码没有显式验证。随机中枢对互异元素可得到期望线性选择时间,但分区把等值全部放左侧,所有键相等时仍可能每次只缩小一项,导致二次时间。
75指出可将尾递归改写为循环:每轮分区后更新 left、right 和必要时的 k,命中目标后返回索引。这样可避免递归栈增长,但不会消除重复键导致的分区退化。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 快速选择维护相对子区间的秩
- · 驱动因素
原书出处 · 2 处
- · 查看原书依据
selectKth是一个平均时间为线性的函数,给定一个适当的pivotIndex,其返回了数组ar中的第k个元素,例4-4是它的一个实现。 例4-4:selectKth的C语言递归实现 selectKth函数必须为数组A[left,right]选出pivotIndex来在递归中使用。如何选择这里存在
- · 查看原书依据
尾递归结构,一个非递归的实现会更直接一些。
参考来源
- 位置:《算法技术手册》第4章《使用环境》(spine1502;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1465.html;u074-ch04-013)。
- 结论依据:74全文和03198完整选择代码实读;重复键退化由分区条件推导,未运行程序。
- 原始内容:selectKth是一个平均时间为线性的函数,给定一个适当的pivotIndex,其返回了数组ar中的第k个元素,例4-4是它的一个实现。 例4-4:selectKth的C语言递归实现 selectKth函数必须为数组A[left,right]选出pivotIndex来在递归中使用。如何选择这里存在
- 位置:《算法技术手册》第4章《驱动因素》(spine1503;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1466.html;u075-ch04-013)。
- 结论依据:75指出可将尾递归改写为循环:每轮分区后更新 left、right 和必要时的 k,命中目标后返回索引。这样可避免递归栈增长,但不会消除重复键导致的分区退化。
- 原始内容:尾递归结构,一个非递归的实现会更直接一些。