用某种算法求中位数 设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数.设计一个算法,找出X和Y的2n个数的中位数...分析算法思路,讲的具体点!（我学的是C++……）谢谢了!
第1个回答 2020-06-10
问题等同于寻找X和Y的2n个数中,第n和n+1大的数.假设X和Y都是升序排列的,最简单的方法就是不断删除两个数组各自首元素的较小者,一直删除
n-1
次,剩下的最小和次小数,就是目标了.但是这个算法的时间复杂度是
O(n)
的.
n-1
次,剩下的最小和次小数,就是目标了.但是这个算法的时间复杂度是
O(n)
的.
