查找所有产品等于目标数量的对

Question

我知道有一个遍历每个数字的详尽解决方案，但如何实施分而治之的方法？

使用一个没有重复数字的整数数组和一个目标乘积整数，return一组数字，其中包含乘积等于目标数字的所有对。

 def product_pair(num_arr, product):
            """
            :type num_arr: List[int]
            :type product: int
            :rtype: List[int]
            """
        Example 1. Product_pair([3, 5, 9, 10, 23, 53], 20) => []
        Example 2. Product_pair([10, 2, 9, 30, 5, 1], 10) => [10, 2, 5, 1]

Answer 1

您可以按如下方式进行：

def f(lst, n):
    lst = list(filter(lambda x: x<=n, lst))  # Note 3
    res = []
    seen = set()
    for i, x in enumerate(lst[:-1]):  # Note 4
        if x in seen:
            continue
        rem = n / x
        if rem in lst[i+1:]:  # Note 1, 2
            seen.add(rem)
            res.extend([x, int(rem)])
    return res

对于您的示例，生成：

print(f([3, 5, 9, 10, 23, 53], 20))  # -> []
print(f([10, 2, 9, 30, 5, 1], 10))  # -> [10, 1, 2, 5]

备注

优化会员测试；您只在当前元素之后的列表切片中查找成员资格。如果以前有的话，你早就找到了
我在这里假设您的候选人列表只包含整数。
您可以过滤掉大于目标数字的数字。那些是不可能找到一个整数互补的。
从注释 1 可以看出，当到达列表中的最后一个数字时，就没有您还没有找到的任何东西。

一般

原始列表中的重复项：例如，有两个 4 不会 return 一个 (4, 4) 目标数量 16 的结果。
这绝对不是最快的，但也不算太慢。

Answer 2

好吧，我不太确定分而治之，但这会非常有效且非常简单：

def product_pair(num_arr, product):
    value_set = set(num_arr)
    sol = [n for n in num_arr if product/n in value_set]
    return sol

查找所有产品等于目标数量的对

Finding all pairs that have the product equal to the target number

python

algorithm

divide-and-conquer

data-structures