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

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

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


这个解决方案的时间复杂度是O(klogk) 空间复杂度是O(k),如果k趋近于m*n .... 靠还不如brute force

肯定有更好的,不过我找不出来
回复

使用道具 举报

🔗
darksteel 2011-5-9 13:26:28 | 只看该作者
全局:
回复 21# wwwyhx
klogk没错,但brute force不是就是把所有n*m个数都排序然后取前k个吗?这样复杂度是nmlog(nm)。只能说k越趋近于n*m这个方法就越接近朴素方法,不可能更差啊
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-10 12:59:16 | 只看该作者
全局:
回复  wwwyhx
klogk没错,但brute force不是就是把所有n*m个数都排序然后取前k个吗?这样复杂度是nmlog(nm)。只能说k越趋近于n*m这个方法就越接近朴素方法,不可能更差啊
darksteel 发表于 2011-5-9 13:26


当然不如,如果k趋近于m*n, m*n*log(m*n)的时间。
而brute force对于m*n个数来说,取第k大的事件复杂度为O(m*n), n个数求第k大的数的时间复杂度是O(n)记得吗,二分法
回复

使用道具 举报

🔗
kungfucop 2011-5-10 13:01:25 | 只看该作者
全局:
那个young tableau的应该是最好的办法了。
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-5-10 13:06:35 | 只看该作者
全局:
那个young tableau的应该是最好的办法了。
kungfucop 发表于 2011-5-10 13:01



    请问那个young tablea的方法具体是什么??
回复

使用道具 举报

🔗
darksteel 2011-5-10 13:16:00 | 只看该作者
全局:
回复 25# wwwyhx
就是杨氏矩阵。。。你说的没错,如果只要找一个数,还真不如在n*m个元素中用random selection。如果是要找出前k个,那杨氏矩阵的方法应该就比较好用了
回复

使用道具 举报

🔗
sing1ee 2012-9-30 16:57:02 | 只看该作者
全局:
如果是从大到小第k个,就好办多了。
回复

使用道具 举报

🔗
sandandfoam 2012-10-30 19:25:29 | 只看该作者
全局:
本帖最后由 sandandfoam 于 2012-10-31 16:01 编辑
darksteel 发表于 2011-5-7 08:10
回复 8# danielgao
初始a(1)+b(1)在堆里,然后每次从堆上弹出一个元素,假设它是a(i)+b(j),那就把a(i+1) ...

9#正解。可以保证堆的大小不超过n,对于每个b(j),堆中最多只有一个a(i)+b(j)与其对应,这样再k较小的时候是O(klogn)时间复杂度,O(n)空间复杂度

当k较大时此方法效率低,可以利用Young Tableau查找方法,对一个数m,杨氏表可以用O(n)复杂度查找出m的位置,以及有多少个数严格大于m,多少个数严格小于m。这样对最小的a(1)+b(1)和最大的a(n)+b(n)之间的数进行二分查找知道该数正好是第K大的数。复杂度为O(nlog(a(n)+b(n)-a(1)-b(1))).

回复

使用道具 举报

🔗
nooneknow 2012-11-5 05:53:54 | 只看该作者
全局:
印象中像是cracking code interview里边的一道题。
回复

使用道具 举报

🔗
vng 2013-3-24 10:10:47 | 只看该作者
全局:
int getMaxKSum(int *a, int la, int *b, int lb, int K)
{
        int nd = 1, oa = 0, ob = 0 ;
        int ai = 1, bi = 1;

        int sum = a[oa] + b[ob];

        if( K > la * lb ) return -1 ; //not found;

        while(nd != K)
        {
                if(ai >= la) { ai = oa; ob++; }
                if(bi >= lb) { bi = ob; oa ++ ;}

                if(a[oa] + b[bi] >= b[ob] + a[ai])
                { sum = a[oa] + b[bi] ;   bi ++; }
                else
                { sum = b[ob] + a[ai] ;   ai ++ ;}
                nd++;
        }

        return sum;

}
回复

使用道具 举报

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

本版积分规则

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