📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : 两个排序数组中求第k大的sum(a+b)

 
🔗
 楼主| wwwyhx 2011-5-7 22:05:48 | 只看该作者
全局:
这是我在网上找的解答,大家看看:

答案:

举个例子:将两个数组合并从大到小降序排,假如如下

a1 a2 b1 b2 a3 b3 a4 a5 b4 b5 (对应的新下标是1至10)

新下标与老下标的差的序列为

0 0 2 2 2 3 3 3 5 5

现在假设要求第10大的sum,那么2+2+2+3=9, 2+2+2+3+3=12,那么由于9<10<12,那么12对应的是第二个3,也就是a4,那么第十大的就是a4+b(10-9),也就是a4+b1。
回复

使用道具 举报

🔗
darksteel 2011-5-8 00:39:09 | 只看该作者
全局:
回复 11# wwwyhx
这个方法的原理是什么呢?而且感觉正确性不那么显然啊,假如a,b排序之后的顺序是:
a1 a2 b1 b2
求第二大的sum。按照上面的方法,答案似乎在给出排序序列之后就确定了。
但对于5 3 2 1和5 4 3 1这两种情况,答案是不一样的啊。是我理解有问题吗?
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-8 00:57:21 | 只看该作者
全局:
回复  danielgao
初始a(1)+b(1)在堆里,然后每次从堆上弹出一个元素,假设它是a(i)+b(j),那就把a(i+1)+b(j)和a(i)+b(j+1)加入堆中。每次加入堆中的元素依赖于当前堆顶的元素。需要用一些手段保证不加入重复的元素。
据说是借鉴了杨氏矩阵的思想。我不能直接看出正确性,希望有人明白的话能说说为什么这样是对的,为什么不会漏掉candidates?
darksteel 发表于 2011-5-7 08:10



    因该是错的,下一个还有可能是相隔较远的数的和。
    网上搜了半天,没看到合适的解答
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-8 01:00:12 | 只看该作者
全局:
回复  wwwyhx
这个方法的原理是什么呢?而且感觉正确性不那么显然啊,假如a,b排序之后的顺序是:
a1 a2 b1 b2
求第二大的sum。按照上面的方法,答案似乎在给出排序序列之后就确定了。
但对于5 3 2 1和5 4 3 1这两种情况,答案是不一样的啊。是我理解有问题吗?
darksteel 发表于 2011-5-8 00:39



  恩  他的解答是错的
回复

使用道具 举报

🔗
darksteel 2011-5-8 01:20:58 | 只看该作者
全局:
回复 13# wwwyhx
我在9楼说的那个可能是对的,我是在一个论坛上看见不止一个人说到这个方法。直观上觉得可能漏掉东西,但仔细一想却找不出什么漏洞。你所说的相隔较远的两个数如果确实可能,那应该已经在堆里,如果不在堆里,就说明在下一轮还不可能。只不过正确性确实不好证明。附一个杨氏矩阵的链接:
http://blog.csdn.net/michealmeng ... /05/28/2489923.aspx
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-8 02:02:45 | 只看该作者
全局:
回复  wwwyhx
我在9楼说的那个可能是对的,我是在一个论坛上看见不止一个人说到这个方法。直观上觉得可能漏掉东西,但仔细一想却找不出什么漏洞。你所说的相隔较远的两个数如果确实可能,那应该已经在堆里,如果不在堆里,就说明在下一轮还不可能。只不过正确性确实不好证明。附一个杨氏矩阵的链接:
darksteel 发表于 2011-5-8 01:20



    因该漏掉了不少,比如第s个是i,j 那么对所有的(a,b)(a>i,b<j) (c,d)(c<i,d>j)都有可能是第s+1个,而非那相邻的两个。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-8 02:09:13 | 只看该作者
全局:
回复  wwwyhx
我在9楼说的那个可能是对的,我是在一个论坛上看见不止一个人说到这个方法。直观上觉得可能漏掉东西,但仔细一想却找不出什么漏洞。你所说的相隔较远的两个数如果确实可能,那应该已经在堆里,如果不在堆里,就说明在下一轮还不可能。只不过正确性确实不好证明。附一个杨氏矩阵的链接:
darksteel 发表于 2011-5-8 01:20



刚知道那个东西叫杨氏矩阵....
想到过,但还是不知道怎么解,对于一点来说只能确定至少比多少个数大,至少比多少个数小,总有一半的面积处于未知状态。

这样把,题目换成在m*n的杨氏矩阵(每行每列递增)中,如何找出第k个大的数,看有没有人会解
回复

使用道具 举报

🔗
darksteel 2011-5-8 02:26:22 | 只看该作者
全局:
回复 16# wwwyhx
不不,我刚才又仔细想了下,好像没漏,并不是所有那些(a,b)都有可能,因为有一些肯定更小的值还在堆里,说明还轮不到他们。。。这么说很难说清楚,如果把上面说的扩展过程放到杨氏矩阵里,开始只有左上角一个元素,然后相当于扩展出一条边界,这个边界上的每个元素就正好是下一个元素的candidates的集合。边界里面的元素已经用过了,而外面的元素肯定不会是当前的candidate,因为你能在边界上找到一个肯定比它小的元素(同一行同一列),而这个元素还没有出堆,说明堆中还有更小的元素。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-8 16:34:11 | 只看该作者
全局:
回复  wwwyhx
不不,我刚才又仔细想了下,好像没漏,并不是所有那些(a,b)都有可能,因为有一些肯定更小的值还在堆里,说明还轮不到他们。。。这么说很难说清楚,如果把上面说的扩展过程放到杨氏矩阵里,开始只有左上角一个元素,然后相当于扩展出一条边界,这个边界上的每个元素就正好是下一个元素的candidates的集合。边界里面的元素已经用过了,而外面的元素肯定不会是当前的candidate,因为你能在边界上找到一个肯定比它小的元素(同一行同一列),而这个元素还没有出堆,说明堆中还有更小的元素。
darksteel 发表于 2011-5-8 02:26



    没错,那个解法是对的。可以这么看:
对于k以内的所有排号为x的组合(i,j),存在(i-1,j)和(i,j-1)在x之前。
也就是说k内任何一个A(i,j),它在一个(i-1,j)和一个(i,j-1)的后面。
换句话说,任何一个在k内的x(i,j),它的(i+1,j);(i,j+1)可能有0个一个或两个在k内(废话),越前面(数越小)的几率越大。用那个最小堆的方法可以实现pop出前k个和,每次都pop出最小的数,同时push in 两个最有可能的候选和
回复

使用道具 举报

🔗
darksteel 2011-5-8 22:28:03 | 只看该作者
全局:
回复 19# wwwyhx
嗯,应该是不会漏的了。。当时第一眼看见也觉得肯定没那么直接,这题看着容易但一般平凡的方法都会漏东西。放在矩阵上一看,才发觉这样边界逐步向外扩展实在非常巧妙
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表