O(n) 算法来找到 n² 隐式数字的中位数 [英] O(n) algorithm to find the median of n² implicit numbers

问题描述

问题:输入是一个(不一定排序)序列 S = k1, k2, ..., kn 的 n 个任意数字.考虑形式为 min{ki,kj} 的 n² 数的集合 C，对于 1 <=i, j<=n.提出一个O(n)时间和O(n)空间的算法来求C的中值.

Problem: input is a (not necessarily sorted) sequence S = k1, k2, ..., kn of n arbitrary numbers. Consider the collection C of n² numbers of the form min{ki,kj}, for 1 <=i, j<=n. Present an O(n) time and O(n) space algorithm to find the median of C.

到目前为止，我通过检查不同集合 S 的 C 发现，C 中 S 中最小数的实例数等于 (2n-1)，下一个最小数:(2n-3) 等等直到你只有一个最大数字的实例.

So far I've found by examining C for different sets S that the number of instances of the smallest number in S in C is equal to (2n-1), the next smallest number: (2n-3) and so on until you only have one instance of the largest number.

有没有办法利用这些信息来找到 C 的中位数?

Is there a way to use this information to find the median of C?

推荐答案

有多种可能性.我喜欢的是 Hoare 的 Select 算法.基本思想类似于快速排序，不同之处在于当您递归时，您只递归到将保存您要查找的数字的分区.

There are a number of possibilities. One I like is Hoare's Select algorithm. The basic idea is similar to a Quicksort, except that when you recurse, you only recurse into the partition that will hold the number(s) you're looking for.

例如，如果您想要 100 个数字的中位数，您可以从对数组进行分区开始，就像在快速排序中一样.你会得到两个分区——其中一个包含第 50^th 个元素.在该分区中递归执行您的选择.继续直到您的分区只包含一个元素，这将是中位数(请注意，您可以对您选择的另一个元素执行相同的操作).

For example, if you want the median of 100 numbers, you'd start by partitioning the array, just like in Quicksort. You'd get two partitions -- one of which contains the 50^th element. Recursively carry out your selection in that partition. Continue until your partition contains only one element, which will be the median (and note that you can do the same for another element of your choice).

这篇关于O(n) 算法来找到 n² 隐式数字的中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！