python - 给定一个包含多个元素的列表，如何获得完美三元组的数量？

Question

我正在尝试解决一个编程问题，给定一个整数列表，找出完美三元组 [x, y, z] 的数量，其中 y % x == 0 和z % y == 0

例如，[1, 2, 3, 4, 5, 6] 有三元组:[1, 2, 4], [1 , 2, 6], [1, 3, 6], 使答案总数为 3.

这是我目前所拥有的:

def solution(l):
    l.sort()
    l.reverse()
    l_size = len(l)
    count = 0

    if len(l) < 3:
        return count

    for i in xrange(len(l) - 2):
        for j in xrange(i + 1, len(l) - 1):
            if l[i] % l[j] == 0:
                for k in xrange(j + 1, len(l)):
                    if l[j] % l[k] == 0:
                        count += 1

    return count

我的解决方案的问题是 l 的长度可能在 2 到 2000 之间(含)。所以对于较长的输入来说需要很长时间。

Answer 1

如果您只需要一个计数而不是实际的三元组，您可以在 O(n^2) 时间内完成。首先创建一个列表，指示列表中有多少其他数字可以平均分配该数字。这需要 O(n^2) 时间。

然后从最大开始迭代数字以找到所有 z、y 对，并为每一对添加创建列表中 y 的值在结果的第一步。这也需要 O(n^2) 时间。

def solution(l):
    divs = [0] * len(l)

    for i in range(len(l)):
        for j in range(i + 1, len(l)):
            if l[j] % l[i] == 0:
                divs[j] += 1

    result = 0
    for i in range(len(l) - 1, 1, -1):
        for j in range(i - 1, 0, -1):
            if l[i] % l[j] == 0:
                result += divs[j]

    return result

print(solution([1, 2, 3, 4, 5, 6]))
print(solution(list(range(1, 2000))))

输出:

3
40777

更新这是另一种一次性处理列表的解决方案:

def solution2(l):
    divs = [[0, 0] for _ in l]

    for i in range(len(l)):
        for j in range(i + 1, len(l)):
            if l[j] % l[i] == 0:
                divs[j][0] += 1
                divs[j][1] += divs[i][0]

    return sum(x[1] for x in divs)