如何减少执行时间（Python）

Question

我试图解决这个问题：https://www.hackerrank.com/tests/2h92ckdchlg/ （我的工作是计算所有过滤间隔中的频率值）

但在代码执行10秒后，我将面临一个“由于超时而终止”的问题。你知道吗

我的解决方案是：

def countSignals(frequencies, ranges):
    ranges = [range(i[0], i[1] + 1) for i in ranges]
    return sum(1 if all(f in r for r in ranges) else 0 for f in frequencies)


if __name__ == '__main__':

    frequencies_count = int(input().strip())

    frequencies = []

    for _ in range(frequencies_count):
        frequencies_item = int(input().strip())
        frequencies.append(frequencies_item)

    filterRanges_rows = int(input().strip())
    filterRanges_columns = int(input().strip())

    filterRanges = []

    for _ in range(filterRanges_rows):
        filterRanges.append(list(map(int, input().rstrip().split())))

    result = countSignals(frequencies, filterRanges)

    print(result)

我只能编辑countSignal函数！你知道吗

我的代码如何运行：

我收到一个数字，相当于len（频率）。在那之后，我得到将组成频率列表的每个元素。然后我接收len（filterges）和组成矩阵filterges的每个列表的维数。最后，我得到组成每个列表的值。你知道吗

输入示例：

5 #-> len(frequencies)
20 #-> frequencies[0]
5 #-> frequencies[1]
6 #-> frequencies[2]
7 #-> frequencies[3]
12# -> frequencies[4]
3 #-> len(filterRanges) -> filterRanges is a matrix
2 #-> lenght of the lists that compose filterRanges
10 20 #-> filterRanges[0] = [10,20]
5 15 #-> filterRanges[1] = [5,15]
5 30 #-> filterRanges[2] = [5,30]

例如，在本例中，它将返回1，因为只有“12”适合所有间隔。你知道吗

我已经用这个代码完成了15个测试中的12个，在最后3个测试中出现了超时错误。我如何优化我的代码，使我能够通过所有这些测试？你知道吗

谢谢！：）

Answer 1

已编辑。 将以O（n+m）运行。只是合并重叠的间隔。你知道吗

#filter contains time intervals
#frequencies contains the elements
#example -> filter = [[1,50],[15,23],[16,40],[8,45],[14,56]]
start = -1
end = 10000000000
flag = True
l = list()
for i in range(len(filter)-1):
    temp = filter[i]
    temp1 = filter[i+1]
    if temp[0] <= temp1[0] <= temp[1]:
        start = max(start,temp[0])
        end = min(end,temp1[1],temp[1])
    elif temp1[0] <= temp[0] <= temp1[1]:
        start = max(start,temp[0])
        end = min(end,temp1[1],temp[1])
    else:
        flag = False
        #print("cant be done")
        break
if flag:
        #print(start,end)
    for i in frequencies:
        if start <= i <= end:
        l.append(i)

return l

Answer 2

看看你的例子：

frequencies = [20, 5, 6, 7, 12]
ranges = [[10,20], [5,15], [5,30]]

您试图解决的问题是确定frequencies列表中有多少项满足条件10 <= f <= 15，其中f是频率，10是范围的最大起始值，15是范围的最小结束值。您首先需要确定此条件检查的上限和下限。你知道吗

lower_bound = None
upper_bound = None
for r in ranges:
    if lower_bound is not None:
        lower_bound = max(lower_bound, r[0])
    else:
        lower_bound = r[0]
    if upper_bound is not None:
        upper_bound = min(upper_bound, r[-1])
    else:
        upper_bound = r[-1]

现在您可以遍历frequencies列表并计算满足条件的频率。有一种特殊情况，下界可能大于上界，在这种情况下没有解，因此返回值应该是0。你知道吗

count = 0
if (lower_bound < upper_bound):
    for f in frequencies:
        if lower_bound <= f <= upper_bound:
            count += 1

这可能已经足够了，但是如果列表中有重复项，那么您将浪费时间检查它们-collections.Counter将是一个很好的选项，用于涵盖此场景。你知道吗

import collections
freq_counter = collections.Counter(frequencies)
count = 0
if (lower_bound < upper_bound):
    for f in freq_counter.keys():
        if lower_bound <= f <= upper_bound:
            count += freq_counter[f]

现在剩下的就是返回count的值。你知道吗

return count