搜狗2014年笔试题-两递增数组A和B,求A[i]+B[j]中前k个最小值

 

在上图中，加入找到最小的组合是12+9，那么接下来放进去的应该是12+10和13+9，哪为什么只放进去了12+10？

这是因为，比13+9小的还有13+-5,13+-2,13+0，如果前面的13+0已经在堆里弹出去了，那么13+9已经在堆里了。如果13+0根本就没在堆里，那么13+9比13+0还要大就更不应该在堆里了。如果13+0在堆里，那么说明13+0不是目前最小的，那么13+9就没有进堆里的必要了。

在11+-5弹出堆的时候，11+-2和12+-5都要进堆，因为二者都有可能是目前最小的。因为12+-5是以12开头的最小的数。

class P():
    def __init__(self,a,b,sum):
        self.a = a
        self.b = b
        self.sum = sum
    def __lt__(self, other):
        if self.sum<other.sum:
            return True
        else:
            return False


def mink_sum(A,B,K):
    i,j,k =0,0,0
    h=[]
    res = []
    heapq.heappush(h,P(0,0,A[0]+B[0]))
    while k<K and h:
        p = heapq.heappop(h)
        print(p.a,p.b,p.sum)
        res.append(p.sum)
        k+=1
        if p.b+1<len(B):
            heapq.heappush(h,P(p.a,p.b+1,A[p.a]+B[p.b+1]))
        if p.b==0:
            if p.a+1<len(A):
                heapq.heappush(h,P(p.a+1,0,A[p.a+1]+B[0]))
    return res
A = [10, 11, 12, 13, 17, 30]
B = [-5, -2, 0, 9, 10, 43]
print(mink_sum(A,B,10))