用某种算法求中位数设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数.设计一个算法,找出X和

用某种算法求中位数
设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数.设计一个算法,找出X和Y的2n个数的中位数...分析算法思路,讲的具体点!(我学的是C++……)谢谢了!
野人闲语 1年前 已收到2个回答 举报

suki_16 幼苗

共回答了24个问题采纳率:91.7% 举报

问题等同于寻找X和Y的2n个数中,第n和n+1大的数.假设X和Y都是升序排列的,最简单的方法就是不断删除两个数组各自首元素的较小者,一直删除 n-1 次,剩下的最小和次小数,就是目标了.但是这个算法的时间复杂度是 O(n) 的.

1年前

10

丁木子 幼苗

共回答了4个问题 举报

将X 和 Y 放入数组 Z 中。然后将Z排序,变成一个新的有序数组,
此时取中间那个元素就可以了。

1年前

1
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.022 s. - webmaster@yulucn.com