3

你有两个列表，你必须找出构成完美正方形的对。

例如在：

a = [2, 6, 10, 13, 17, 18]

b = [3, 7, 8, 9, 11, 15]

有两对(2,8)和(8,18)。

有没有比蛮力更有效的方法？这是我的代码，其时间复杂度为 O(n*m)（其中 n 是 a 的长度，m 是 b 的长度）。

pl = []
a = [ 2, 6, 10, 13, 17,18]
b = [ 3, 7, 8, 9, 11, 15 ]
i = 0
while(i < len(a)):
    j = 0
    while(j < len(b)):
        p = a[i]*b[j]
        n = p**0.5
        u = int(n)
        if n == u:
            pl.append((a[i],b[j]))

        j = j+1


    i = i+1

print(pl)

在这里使用 C# 之前已经问过这个问题，但我不明白“我们需要为每个数字存储的只是它的哪个素数具有奇数”的意思，所以我无法在我的 Python 代码。

有人可以向我解释我们如何在 Python 中实现一个有效的解决方案吗？

4

1 回答 1

2

链接问题中描述的逻辑如下。完美正方形的质因数总是成对出现。例如，36 = 2*2*3*3。我们有两个3s 和两个2s。因此，如果我们将任意两个数相乘形成一个完美的平方，如果我们将它们的每个素数相加，我们也会得到偶数。

例如8 = 2*2*2， 和18 = 2*3*3。结合起来，我们得到四个2s 和两个3s。

下面是一些实现此算法的 Python 代码，使用collections.Counter和设置来删除重复项。首先，我们预先计算每个唯一元素的所有素数分解，a以b避免冗余，并将其存储在字典中。然后，我们循环从a和中的元素对b，使用itertools.product，并结合主要因素计数。如果每个计数都是偶数，我们将排序的对添加到一个集合中。

代码：

from collections import Counter
import itertools

def prime_factors(n):
    """
    https://stackoverflow.com/a/22808285/12366110
    """
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return Counter(factors)

a = [2, 6, 10, 13, 17,18]

b = [3, 7, 8, 9, 11, 15]

prime_factors = {i: prime_factors(i) for i in set(a) | set(b)}

rv = set()

for a, b in itertools.product(a, b):
    combined_counts = prime_factors[a] + prime_factors[b]
    if all(v%2 == 0 for v in combined_counts.values()):
        rv.add(tuple(sorted([a, b])))

输出：

>>> rv
{(2, 8), (8, 18)}
于 2020-02-14T11:37:39.650 回答