python - k-最大双重选择

Question

假设您有两个袋子(A 和 B)，里面分别装有 N 和 M 球。每个球都有一个已知的数值(利润)。您需要提取(有替换)总利润最大的一对球(由所选球的乘法给出)。

最佳提取是显而易见的:从 A 和 B 中选择最有值(value)的球。

当你被要求给出第二个或第 k 个最佳选择时，问题就出现了。按照之前的方法，您应该从 A 和 B 中选择最有值(value)的球，而无需重复选择。

这可以通过计算每个可能选择的值、排序和排序来笨拙地解决(Python 中的示例):

def solution(A,B,K):
    if K < 1:
        return 0
    pool = []
    for a in A:
        for b in B:
            pool.append(a*b)
    pool.sort(reverse=True)
    if K>len(pool):
        return 0
    return pool[K-1]

这可行，但其最坏的时间复杂度是O(N*M*Log(M*M))，我敢打赌有更好的解决方案。

我找到了一个基于表的解决方案，其中 A 和 B 元素按从较高值到较低值排序，并且每个值都与表示下一个值的索引相关联从另一列进行测试。最初这个表看起来像:

A 中的第一个元素是 25，必须针对 对其进行测试(index 2 select from b = 0) 20 所以 25*20=500 是第一个最大的选择，在增加要检查的索引后，表格更改为:

使用这些索引，我们可以快速获得最佳选择候选人:

25 * 20 = 500 #first from A and second from B
20 * 20 = 400 #second from A and first from B

我尝试编写此解决方案:

def solution(A,B,K):
    if K < 1:
        return 0
    sa = sorted(A,reverse=true)
    sb = sorted(B,reverse=true)

    for k in xrange(K):
        i = xfrom
        j = yfrom
        if i >= n and j >= n:
                ret = 0
                break
        best = None
        while i < n and j < n:
                selected = False
                #From left
                nexti = i
                nextj = sa[i][1]
                a = sa[nexti][0]
                b = sb[nextj][0]
                if best is None or best[2]<a*b:
                        selected = True
                        best = [nexti,nextj,a*b,'l']
                #From right
                nexti = sb[j][1]
                nextj = j
                a = sa[nexti][0]
                b = sb[nextj][0]
                if best is None or best[2]<a*b:
                        selected = True
                        best = [nexti,nextj,a*b,'r']
                #Keep looking?
                if not selected or abs(best[0]-best[1])<2:
                        break
                i = min(best[:2])+1
                j = i
                print("Continue with: ", best, selected,i,j)
        #go,go,go
        print(best)
        if best[3] == 'l':
            dx[best[0]][1] = best[1]+1
            dy[best[1]][1] += 1
        else:
            dx[best[0]][1] += 1
            dy[best[1]][1] = best[0]+1
        if dx[best[0]][1]>= n:
            xfrom = best[0]+1
        if dy[best[1]][1]>= n:
            yfrom = best[1]+1
        ret = best[2]

    return ret

但它对在线 Codility 法官不起作用(我是否提到过这是已过期的 Codility 挑战解决方案的一部分？Sillicium 2014)

我的问题是:

• 第二种方法是一个未完成的好解决方案吗？如果是这样的话，我可能会错过什么线索吗？
• 您知道解决该问题的更好方法吗？

Answer 1

您需要维护一个优先级队列。

从 (sa[0], sb[0]) 开始，然后转到 (sa[0], sb[1]) 和 (sa[1]，sb[0])。如果 (sa[0] * sb[1]) > (sa[1] * sb[0])，我们可以说一下 (sa[0], sb[2]) 和 (sa[1], sb[0])?

答案是否定的。因此，我们必须维护一个优先级队列，并且在删除每个 (sa[i], sb[j]) 后(例如 sa[i] * sb[j] 为队列中最大的)，我们必须添加到优先级队列 (sa[i - 1], sb[j]) 和 (sa[i], sb[j - 1] )，然后重复此 k 次。

顺便说一句，我将此算法指定为 answer to a different question 。该算法乍一看可能有所不同，但本质上它解决的是同一个问题。