现在的位置: 首页 > 综合 > 正文

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

2019年04月19日 ⁄ 综合 ⁄ 共 161字 ⁄ 字号 评论关闭

两个数组A,B. 是排好序的,a是A中的元素,b是B中的元素,求第k大的sum(a+b)


先把a[1]+b[1]放入堆中,

每次从堆中取得最小值,设a[i]+b[j],并扩展a[i+1]+b[j] , a[i]+b[j+1]放入堆中


至于为什么要扩展a[i+1]+b[j]
, a[i]+b[j+1],只能说他们俩有较大的概率含有候选集合


抱歉!评论已关闭.