我无法理解分区集S中的元素数量与第k个最小数字的关系 . 假设我有这个伪代码：
Select (k,S)
if |S|=1 then return a in S
Choose random a in S
Let S1,S2,S3 be sets of elements in S (<,=,> to a)
If |S1|>=k then return Select(k,S1)
Else if |S1| + |S2| >= k then return a
Else return Select(k-|S1|-|S2|, S3)
据我所知，为了找到第k个最小元素，我选择一个枢轴并对枢轴周围的数字进行排序，使得所有数字较少位于左侧，所有数字较大位于枢轴右侧 . 然后，如果我想找到第k个最小的数字，我将它与枢轴的位置进行比较，如果枢轴的位置大于k，我看向枢轴的左侧，如果枢轴的位置小于k ，我向右看并从那里递归 .
但是，在上面的伪代码中，我没有看到上面与pivot和k的比较发生在哪里 . 我的意思是，不应该与> = k而不是| S1 |进行比较> = k，因为a是枢轴？
通过与k的比较，集合中元素的数量如何发挥作用？
1 回答
S1是小于a的数字集 . S2是数字的集合== a . S3是数字> = a的集合 . 这已经包含了很多比较 .
现在如果| S1 | > = k，则小于a的数字集超过k个元素 . 因此，最小的k数已经包含在S1中 .
如果不是这种情况，那么它不包含在S1中，因此它必须在S2或S3中 .
如果| S1 | | S2 | > = k，当然它必须在S1或S2中 . 由于它不在S1中，因此必须在S2中 . 由于S2 = ，k最小数是a .
如果不是这种情况，那么它必须在S3中 . 因此，搜索可以限制为S3 . 由于S3中缺少S1和S2中包含的数字，并且由于它们小于S3中的所有数字，这意味着我们必须搜索k- | S1 | - | S2 | . S3中最小的数字 .