python - 求和小于给定阈值时的三元组总数

Question

所以我正在处理一些练习题，但在降低复杂性方面遇到了困难。我得到了一组不同的整数 a[] 和一个阈值 T。我需要找到三元组 i 、 j 、 k 的数量，使得 a[i] < a[j] < a[k] 和 a[i] + a[j] + a[k] <= T 。我已经使用以下 python 脚本将其从 O(n^3) 降低到 O(n^2 log n)。我想知道我是否可以进一步优化它。

import sys
import bisect

first_line = sys.stdin.readline().strip().split(' ')
num_numbers = int(first_line[0])
threshold = int(first_line[1])
count = 0

if num_numbers < 3:
    print count
else:
    numbers = sys.stdin.readline().strip().split(' ')
    numbers = map(int, numbers)
    numbers.sort()

    for i in xrange(num_numbers - 2):
        for j in xrange(i+1, num_numbers - 1):
            k_1 = threshold - (numbers[i] + numbers[j])
            if k_1 < numbers[j]:
                break
            else:
                cross_thresh = bisect.bisect(numbers,k_1) - (j+1)
                if cross_thresh > 0:
                    count += cross_thresh

    print count

在上面的示例中，第一行输入仅提供数字的数量和阈值。下一行是完整列表。如果列表小于 3，则没有可以存在的三元组，因此我们返回 0。如果不是，我们读取完整的整数列表，对它们进行排序，然后按如下方式处理它们:我们遍历 i 的每个元素和 j(这样 i < j)，我们计算不会破坏 i + j + k <= T 的 k 的最高值。然后我们找到列表中第一个违反此条件的元素的索引 (s)，并将 j 和 s 之间的所有元素添加到计数中。对于一个列表中的 30,000 个元素，这大约需要 7 分钟才能运行。有什么方法可以让它更快吗？

Answer 1

您正在对每个 (i,j) 对执行二进制搜索，以找到 k 的对应值。因此 O(n^2 log(n))。

我可以建议一个最坏情况下时间复杂度为 O(n^2) 的算法。

假设列表从左到右排序，元素编号从 1 到 n。那么伪代码是:

for i = 1 to n - 2:
    j = i + 1
    find maximal k with binary search
    while j < k:
        j = j + 1
        find maximal k with linear search to the left, starting from last k position

最坏情况下时间复杂度为 O(n^2) 而不是 O(n^3) 的原因是位置 k 单调递减。因此，即使使用线性扫描，您也不会为每个 (i,j) 对花费 O(n)。相反，您总共花费了 O(n) 时间来扫描每个不同的 i 值的 k。