两个有序数序列中找第k小

所需积分/C币:15 2013-11-20 22:30:53 2KB CPP
收藏 收藏
举报

已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为n, 现在请你用分治算法,找出X和Y的第k小的数,算法时间复杂度为O(max{logm, logn})。 此题请勿采用将序列X和Y合并找第k小的O(m+n)的一般方法,要充分利用X和Y已经排好序的这一特性。 输入格式 第一行有三个数,分别是长度m、长度n和k,中间空格相连(1<=m,n<=100000; 1<=k<=m+n)。 第二行m个数分别是非减序的序列X。第三行n个数分别是非减序的序列Y。 输出格式 序列X和Y的第k小的数。 输入样例 5 6 7 1 8 12 12 21 4 12 20 22 26

...展开详情
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐