给定的实数矩阵,每行和每列都是递增的,求这个数的中位数。
使用类似Tarjan的线性中位数的方法,每次找每列中位数,然后找中位数的中位数,之后可以删除前一半列的上半部分或者后一半列的下半部分,这样可以实现复杂性。
但是这个问题是有的算法的,在Top Language Google Group的Obtuse Sword的指点下,找到了这个问题的原始论文:Generalized Selection and Ranking: Sorted M...
给定的实数矩阵,每行和每列都是递增的,求这个数的中位数。
使用类似Tarjan的线性中位数的方法,每次找每列中位数,然后找中位数的中位数,之后可以删除前一半列的上半部分或者后一半列的下半部分,这样可以实现复杂性。
但是这个问题是有的算法的,在Top Language Google Group的Obtuse Sword的指点下,找到了这个问题的原始论文:Generalized Selection and Ranking: Sorted M...