我必须实现一个解决多选问题的算法。多选问题是：
给定从线性有序集合中抽取的 n 个元素的集合 S，以及介于 1 和 n 之间的正整数的集合 K = {k1, k2,...,kr}，多选问题是选择第 k 个最小的元素对于 i 的所有值，1 <= i <= r
我需要解决 Θ(n log r) 上的平均情况我找到了一篇实现我需要的解决方案的论文，但它假设集合 S 上没有重复的数字。问题是我不能假设那我不知道如何调整该论文的算法以支持重复数字。论文在这里：http ://www.ccse.kfupm.edu.sa/~suwaiyel/publications/multiselection_parCom.pdf 算法在第二页。欢迎任何提示！
后人：Ivan所指的算法是对K进行排序，然后递归解决问题如下。使用 QuickSelect 找到第 k 个最小的元素 x，其中 i 是 ceil(r/2)，然后在 K 和 S 的较小部分以及 K 和 S 的较大部分上递归，将 K 关于 i 拆分，将 S 关于 x 拆分。
寻找在存在退化（这里是相等元素）的情况下工作的算法对于理论著作的作者来说通常不是高优先级，因为它使常见情况的呈现更加困难，并且通常不会在确定计算中发挥作用问题的复杂性。这本质上是一个一维问题，黑盒解很容易；将输入 yi 的第 i 个元素替换为 (yi, i) 并使用第二个组件在比较中打破平局。
在实践中，我们可以做得更好。不是在 {y : y in S, y < x} 和 {y : y in S, y > x} 上递归，而是使用关于 x 的三向分区算法（例如，参见 QuickSort 的每个足够完整的处理），然后将数组 S 除以索引而不是值。