algorithm - 快速选择说明

Question

在这张快速选择的演讲幻灯片中，“ k ”到底是什么意思？

Answer 1

假设你拿了一个号码x。

设L为小于x数组中的数字集合，集合的大小为|L|

设E是数组中等于的数字集合，集合的x大小为|E|

设G为大于x数组中的数字集合，集合的大小为|G|

让我们想象一下排序后的数组，第一个|L|数字(1 -> |L|)包含在 set 中L。

以下|E|数字(|L|+1 -> |L|+|E|)包含在 set 中E。

以下|G|数字(|L|+|E|+1 -> end)包含在 set 中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 -> end)在排序数组中的位置之间，所以它是'G'中的一个元素。由于已经有|L|+|E|小于kth最小数字的数字，我们可以|L|+|E|从中减去k，我们称之为k'( k' = k - |L| - |E|)，然后在 中搜索k'th最小元素G。