快速选择澄清

假设你拿了一个号码 x .

允许 L 是一组小于 x个 在数组中,集合的大小为 |L|

允许 E 是一组数字,等于 x个 在数组中,集合的大小为 |E|

允许 G 是大于 x个 在数组中,集合的大小为 |G|

让我们想象一下排序后的数组 |L| 数字 (1 -> |L|) 包含在集合中 L .

以下内容 |E类| 数字 (|L|+1 -> |L|+|E|) 包含在集合中 E .

以下内容 |G级| 数字 (|L|+|E|+1 -> end) 包含在集合中 G .

我们正在寻找 kth 最小数量,因此我们有3个案例:

1) k <= |L| 这意味着我们要找的数字在第一位 |L| 排序数组中的数字,因此我们搜索 kth公司 中的最小数字 L .

2) |L| < k <= |L|+|E| 这意味着我们要查找的数字介于 (| L |+1->| L |+| E |) 在排序数组中,因此它是 E . 由于 E 等于 x个 ,我们知道 kth公司 最小值等于 x个 .

3) k > |L|+|E| 这意味着我们要查找的数字介于 (| L |+| E |+1->结束) 在排序数组中,因此它是来自“G”的元素。因为已经有了 |L|+|E| 数字小于 kth公司 最小的数字,我们可以减去 |L |+| E| 从…起 k ,我们叫它 k' ( k' = k - |L| - |E| ),并搜索 k'th 中的最小元素 G .