问题:输入是一个(不一定是排序的)序列S = k1,k2,...,n个任意数的kn.考虑形式为min {ki,kj}的n 2个数的集合C,对于1 <= i,j <= n.提出一个O(n)时间和O(n)空间算法来找到C的中位数.
到目前为止,通过检查C的不同集合S,我发现C中S中最小数字的实例数等于(2n-1),下一个最小数字:(2n-3),依此类推,直到你只有一个最大数字的实例.
有没有办法使用这些信息来找到C的中位数？
Jer*_*fin 19
有很多种可能性.我喜欢的是Hoare的Select算法.基本的想法类似于Quicksort,除了当你递归时,你只能递归到将保存你正在寻找的数字的分区.
例如,如果你想要100个数字的中位数,你可以从分区数组开始,就像在Quicksort中一样.你会得到两个分区 - 其中一个包含第50 个元素.递归地在该分区中执行您的选择.继续,直到您的分区只包含一个元素,这将是中位数(并注意您可以为您选择的另一个元素执行相同操作).
是的,好拼图.我们可以在您说的线上找到中位数.
在C中,我们有1次出现max(k),3次出现次高,5次出现最高等等
如果我们对C的元素进行排序,则第m个最大数左边的元素数是m ^ 2(奇数之和)
我们感兴趣的数字(计算中位数)a.如果n是奇数,则是(n ^ 2 + 1)/ 2 =αb.如果n是偶数,那么alpha1 = n ^ 2/2且alpha2 = n ^ 2/2 + 1但alpha1 = n ^ 2/2绝不是方数=> alpha1右边的数字等于alpha1(前m个奇数之和为平方)=> alpha1 = alpha2.
因此,归结为确定m使得m ^ 2(前m个奇数的和)刚好高于(n ^ 2/2)
因此,它归结为确定m = ceiling(原始序列中的n/sqrt(2)和第m个最高数.(是否找到第m个最高或第(nm-1)个最低是优化).
我们可以很容易地找到第m个最高数字(只记下左边第一个最大数字)或者使用中位数算法的中位数来计算线性时间.