问题:输入是一个(不一定是排序的)序列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的中位数？
我不得不对数组进行排序以找到它的中位数,但现在我需要恢复数组的初始值,把它放在原样.那可能吗？