arrays - 使用外部函数查找未排序数组中的第 k 个元素

Question

我需要设计一个算法，使用名为“MED3”的函数在未排序的数组中找到第 k 个最小元素：此函数查找数组的 n/3（地板）和 2n/3（天花板）元素（如果已排序） （与中位数非常相似，但不是 n/2 它返回这些值）。

我考虑过围绕这两个值进行分区，而不是像 QuickSelect 那样继续，但问题是“MED3”不返回两个值的索引，只返回值。

例如，如果数组是：1、2、10、1、7、6、3、4、4，则返回 2（n/3 值）和 4（2n/3 值）。

我还想过遍历数组并将 2 到 4 之间的所有值（例如，在上面的给定数组中）放入新数组，然后再次使用“MED3”，但可以重复（如果数组为 2， 2, 2, 2, ..., 2 我每次都会取所有元素）。

有任何想法吗？我必须使用“MED3”。* MED3 就像一个黑匣子，它以线性时间运行。

谢谢你。

Answer 1

我认为您走在正确的轨道上，但是我建议您删除 <= MED3.floor() 的前 n/3 个值和 >= MED3 的前 n/3 个值，而不是取 2 到 4 个.ceil()。这避免了过多重复的问题。如果两次通过/循环不太昂贵，您可以删除所有值 < MED3.floor() + 最多 n/3 个值 = MED3.floor() （对 ceil() 执行相同操作）

然后重复直到你到达第 k 个最小的目标。