如何在数组中找到多个 ki 最小元素

Question

我正在为我的家庭作业而苦苦挣扎，需要一点推动 - 问题是设计一种算法，该算法将在O(nlogm(时间内找到多个最小的元素1<k1<k2<...<kn并且你有m * k。我知道一个简单的选择算法需要 o(n( 时间来找到第 k 个元素，但是您如何减少重复中的 m？我虽然在每次运行中同时做 k1 和 kn，但这只会取出 2，而不是 m/2。

将不胜感激一些方向。谢谢

Answer 1

如果我正确理解了这个问题，你有一个包含 m 个索引的向量 K，并且你想为 K 中的每个 k 找到 A 的第 k 个排名元素。 如果 K 包含最小的 m 个索引(即 k=1,2,...,m(，那么这可以在线性时间 T=O(n( 中轻松完成，方法是使用快速选择查找元素k_m(因为所有较小的元素都将位于快速选择末尾的左侧(。 所以我假设 K 可以包含任何一组 m 索引。

实现此目的的一种方法是同时对所有 K 运行快速选择。 这是算法

QuickselectMulti(A,K)
If K is empty, then return an empty result set
Pick a pivot p from A at random
Partition A into sets A0<p and A1>p.
i = A0.size + 1
if K contains i, then remove i from K and add (i=>p) to the result set.
Partition K into sets K0<i and K1>i
add QuickselectMulti(A0,K0) to the result set
subtract i from each k in K1  
call QuickselectMulti(A1,K1), add i to each index of the output, and add this to the result set
return the result set

如果 K 只包含一个元素，则与随机快速选择相同。 要了解为什么运行时间平均为 O(n log m(，首先考虑当每个枢轴将 A 和 K 精确地分成两半时会发生什么。 在这种情况下，您会收到两个递归调用，因此您有

T = n + 2T(n/2,m/2)
  = n + n + 4T(n/4,m/4)
  = n + n + n + 8T(n/8,m/8)

由于 m 每次都减半，因此n在此求和中将出现 log m 次。 要实际推导出预期的运行时间需要更多的工作，因为你不能假设枢轴会将两个数组分成两半，但如果你通过计算，你会发现运行时间实际上是 O(n log m( 平均。

编辑时：通过运行 p=Quickselect(A，k_i( 来选择枢轴，其中 k_i 是 K 的中间元素，而不是随机选择 p，从而简化此操作。这将保证 K 每次被分成两半，因此递归调用的数量将正好是 log m，并且由于快速选择以线性时间运行，结果仍将是 O(n log m(。