使用外部函数查找未排序数组中的第 k 个元素
Finding the k'th element in unsorted array using external function
我需要设计一个算法，使用调用 "MED3" 的函数找到未排序数组中的第 k 个最小元素：
此函数查找数组的 n/3 (floor) 和 2n/3 (ceil) 元素（如果它已排序）（非常类似于中位数，但不是 n/2 它 return那些值）。
我考虑过围绕这 2 个值进行分区，而不是像 QuickSelect 那样继续，但问题是 "MED3" 没有 return 这 2 个值的索引，只有这些值.
例如，如果数组是：1, 2, 10, 1, 7, 6, 3, 4, 4 它returns 2（n/3值）和4（2 n/3 值）。
我还想 运行 遍历数组并将 2 到 4 之间的所有值（例如，在上面给定的数组中）取到新数组，然后再次使用 "MED3"，但可以重复（如果数组是 2, 2, 2, 2, ..., 2 我每次都会取所有元素）。
有什么想法吗？我必须使用 "MED3"。
* MED3 就像一个黑盒子，线性时间运行s。
谢谢。
我认为您走在正确的轨道上，但我建议您删除第一个 n/3 值 <= MED3.floor() 和第一个值而不是 2 到 4 n/3 个 >= MED3.ceil() 的值。这避免了太多重复的问题。如果两个 passes/cycle 不是太贵，您可以删除所有值 < MED3.floor() + 最多 n/3 个值 = MED3.floor() （做同样的事情对于 ceil())
然后重复，直到你到达第 k 个最小的目标。
我需要设计一个算法，使用调用 "MED3" 的函数找到未排序数组中的第 k 个最小元素： 此函数查找数组的 n/3 (floor) 和 2n/3 (ceil) 元素（如果它已排序）（非常类似于中位数，但不是 n/2 它 return那些值）。
我考虑过围绕这 2 个值进行分区，而不是像 QuickSelect 那样继续，但问题是 "MED3" 没有 return 这 2 个值的索引，只有这些值.
例如，如果数组是：1, 2, 10, 1, 7, 6, 3, 4, 4 它returns 2（n/3值）和4（2 n/3 值）。
我还想 运行 遍历数组并将 2 到 4 之间的所有值（例如，在上面给定的数组中）取到新数组，然后再次使用 "MED3"，但可以重复（如果数组是 2, 2, 2, 2, ..., 2 我每次都会取所有元素）。
有什么想法吗？我必须使用 "MED3"。 * MED3 就像一个黑盒子，线性时间运行s。
谢谢。
我认为您走在正确的轨道上，但我建议您删除第一个 n/3 值 <= MED3.floor() 和第一个值而不是 2 到 4 n/3 个 >= MED3.ceil() 的值。这避免了太多重复的问题。如果两个 passes/cycle 不是太贵，您可以删除所有值 < MED3.floor() + 最多 n/3 个值 = MED3.floor() （做同样的事情对于 ceil())
然后重复，直到你到达第 k 个最小的目标。