我正在解决一些练习问题,但降低复杂度的过程中遇到了麻烦。给定一个不同整数数组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),并计算不会破坏的最高值。然后我们找到第一个违反此条件的列表中的元素的索引
j > lastJ
的迭代,你只需要在范围[0, last_cross_thresh]
中进行搜索。虽然我相当确定这不会在实践中改善渐近复杂度或运行时间。 - j_random_hackerO(n)
时间内)来预先过滤列表,然后消除任何使得两个最小元素的和与该元素的和超过T
的元素(也是一个O(n)
扫描)。即使您的整体算法是O(n^3)
或其他复杂度,这将为您提供一个较小的工作集...预先对列表进行排序(O(n lg n)
)可能会使其更简单... - twalbergif cross_thresh > 0:
的末尾添加一个else <break out of innermost loop>
子句即可。 - j_random_hacker