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 ，我从那里向右看并递归。

但是，在上面的伪代码中，我看不到上面与 pivot 和 k 的比较发生在哪里。我的意思是，它不应该与 >= k 而不是 |S1| 进行比较 >= k，因为 a 是支点？

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

4

1 回答 1

1

S1 is the set of numbers smaller than a. S2 is the set of the numbers == a. And S3 is the set of number >= a. This already contains lots of comparisons.

Now if |S1| >= k, then the set of numbers smaller than a exceeds k elements. Thus the k smallest number is already contained in S1.

If this is not the case, then it is not contained in S1, thus it must be in S2 or S3.

If |S1|+|S2| >= k, then of course it must be in S1 or S2. Since it is not in S1 it must be in S2. Since S2 = {a} the k smallest number is a.

If none of this is the case then it must be in S3. Thus the search can be constrained to S3. Since the numbers contained in S1 and S2 are missing from S3 and since they are smaller than all numbers in S3 this implies that we have to search for the k-|S1|-|S2| smallest number in S3.

于 2013-07-21T10:47:58.110 回答