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

Question

我正在努力完成作业，需要一点推动-问题是设计一个算法，在O（nlogm）时间内找到多个最小元素

希望您能指点一下方向。谢谢

Answer 1

如果我正确理解了这个问题，您有一个包含m个索引的向量K，并且您希望为K中的每个K找到a的第K个排名元素。如果K包含最小的m个索引（即K=1,2，…，m），那么可以通过使用quickselect查找元素K\m（因为所有较小的元素都将位于quickselect末尾的左侧），在线性时间T=O（n）内轻松完成此操作。所以我假设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\u i），其中k\u i是k的中间元素，而不是随机选择p，对该算法的分析可以简化此操作。这将保证每次将K分成两半，因此递归调用的数量将正好是log m，并且由于quickselect在线性时间内运行，因此结果仍然是O（n log m）。