取具有最小和的两个排序数组的前10个乘积

Question

没有设法用谷歌搜索这个问题的名称，希望这个问题对社区有所帮助。

考虑一下我们有两个数字的排序数组，例如：

 2  8
12 18
45 35
85 48
87 49
97 59

并且我们想有效地从两个数组中首先获取数字的k（10）个最小和组合。在我们的情况下是：

 2 +  8 = 10 
 2 + 18 = 20
12 +  8 = 20
12 + 18 = 30
 2 + 35 = 37
12 + 35 = 47
 2 + 48 = 50
 2 + 49 = 51
45 +  8 = 53
12 + 48 = 60

什么是正确的方法？我抓了一个简单的实现（由@sanyash改进），但是它没有利用数组已排序的事实，并且该问题在线性时间内感觉可行...

def smallest_product(k, arr1, arr2):
    product_iter = itertools.product(
        itertools.islice(arr1, k),
        itertools.islice(arr2, k),
    )
    product_sorted = sorted(product_iter, key=sum)
    product_sliced = itertools.islice(product_sorted, k);
    return list(product_sliced)

print(smallest_product(10, 
    [ 2, 12, 45, 85, 87, 98], 
    [ 8, 18, 35, 48, 49, 59]))

类似的问题：efficient sorted Cartesian product of 2 sorted array of integers（但它涉及创建完整的结果数组，而在我的情况下，我只需要前几个值）

P.S。我添加了python标记，因为这是一个数学问题，但是我对任何语言的解决方案，仅仅是一种解释，或者是维基百科的链接都感到满意...

Answer 1

首先将两个数组截断为len k。之后，使用您以前的实现。这将是O（k ^ 2）难度：

import itertools

def smallest_product(k, arr1, arr2):
    product_iter = itertools.product(
        itertools.islice(arr1, k),
        itertools.islice(arr2, k),
    )
    product_sorted = sorted(product_iter, key=sum)[:k]
    return list(product_sorted)


print(smallest_product(
    10, 
    [ 2, 12, 45, 85, 87, 98], 
    [ 8, 18, 35, 48, 49, 59])
)