理解选择算法

Question

理解选择算法

3

我很难理解分区集合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，则查找枢轴右侧，然后递归。

但是，在上面的伪代码中，我不明白枢轴和k之间的比较在哪里发生。我的意思是，它不应该与&a;>= k进行比较吗，而不是|S1| >= k，因为a是枢轴？

集合中元素的数量如何影响与k的比较？

- user1766888

3

让S1、S2和S3是集合S中的元素集合（使用<、=和>进行比较）。后续的内容取决于a>b和c>b意味着c>a。数学又出现了。 - sehe

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Udo Klein · Accepted Answer

S1是小于a的数字集合。S2是等于a的数字集合。S3是大于等于a的数字集合。这已经包含了很多比较。

如果|S1|>=k，则小于a的数字超过了k个。因此，前k个最小的数字已经包含在S1中。

如果不是这种情况，则它不包含在S1中，因此必须在S2或S3中。

如果|S1|+|S2|>=k，则它必须在S1或S2中。由于它不在S1中，因此它必须在S2中。由于S2={a}，所以第k个最小的数字是a。

如果没有一种情况成立，则它必须在S3中。因此，搜索可以限制在S3中进行。由于包含在S1和S2中的数字缺失于S3中，并且它们小于S3中的所有数字，这意味着我们必须在S3中搜索第k-|S1|-|S2|个最小的数字。