知识卡片
第K小依较小分区定位
求第K小元素时,设L为小于枢轴的元素数,先考虑元素互异且K从1计数:K≤L时去较小组,K=L+1时返回枢轴,否则去较大组找第K-L-1小。划分标签必须与大小方向一致;重复值还需单独处理等于枢轴的一组,不能直接套互异元素公式。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
选出一个枢轴元素,将比枢轴元素大的元素放到枢轴元素的右边,将比枢轴元素小的元素放到枢轴元素的左边。这样,N 个数被分成了两部分,比枢轴大一部分记为S (1),比枢轴小的部分记为S (2),这就是分治的“分”。 假设一种理想的情况,枢轴元素基本位于中间值,即它总是将原数组
参考来源
- 位置:《代码精进之路:从码农到工匠(异步图书)》9.1.3 K选择问题(spine2;extracted/代码精进之路:从码农到工匠(异步图书)/_epub-src/OEBPS/text00001.html;u146-ch09-008)。
- 结论依据:原文在“选出一个枢轴元素”附近的定义、实例或代码支撑本卡的核心说明:求第K小元素时,设L为小于枢轴的元素数,先考虑元素互异且K从1计数:K≤L时去较小组,K=L+1时返回枢轴,否则去较大组找第K-L-1小。适用边界按该处前提解释,代码未执行。
- 原始内容:选出一个枢轴元素,将比枢轴元素大的元素放到枢轴元素的右边,将比枢轴元素小的元素放到枢轴元素的左边。这样,N 个数被分成了两部分,比枢轴大一部分记为S (1),比枢轴小的部分记为S (2),这就是分治的“分”。 假设一种理想的情况,枢轴元素基本位于中间值,即它总是将原数组