时间戳

首页 > 解决方案 > 带有嵌套 for 循环的 Python 代码太慢了

python - 带有嵌套 for 循环的 Python 代码太慢了

问题描述

我正在做一个问题。HackerRank这个问题在开始时定义了一个大小为 n 的零数组，然后对其进行操作。所以假设数组是x = [0, 0, 0, 0, 0, 0]. 所以n = 6在这里。现在考虑操作（他们在问题中称其为查询）[1, 2, 5]。这意味着在数组中x，从索引 0 到 1 加 5。所以x现在变成x = [5, 5, 0, 0, 0, 0]。并且可能有很多这样的操作（查询）。最后，我们只需要找到最终数组的最大元素x。所以样本输入是

5 3
1 2 100
2 5 100
3 4 100

所以我们需要x一个大小为 5 的数组（初始化为零），并且有 3 个查询要在其上运行。如果我们通过查询，我们发现最终数组中的最大元素是 200。我在这里使用嵌套 for 循环完成了代码。外部 for 循环遍历查询，内部 for 循环操作数组x。对于数组大小的小值x，我的代码效果很好。但是，当n = 1000000和查询次数时m = 100000，嵌套的 for 循环会永远运行（它就像一个无限循环）。我想知道我怎样才能让它更快。以下是嵌套的 for 循环

# Construct a zero list of length n
worklist = list([0]*n)
# Loop through the queries
for query in queries:
    # Since the problem defines the queries vector
    # as one based index, we need to modify the
    # indices of query
    index0, index1 = query[0]-1, query[1]-1
    # Now construct the new list with addition
    for i in range(index0, index1+1):
        worklist[i] = worklist[i] + query[2]

我想我需要修改我的算法来做到这一点。欢迎提出建议。

标签： pythonarraysalgorithm

解决方案

在这个问题的讨论页面中，有一个 O(n) 的解决方案，这是关于重叠的问题。

基本思路是，你只需要在数组中标记“添加”点和“删除”点，所以最后阶段你只需要遍历数组一次并将“当前总和”保留在当前索引中，你就可以记录最多一个答案。

例如 5 3

1 2 100

2 5 100

3 4 100

您的数组将简化为

0, 0, 0, 0, 0, 0

当获取第一个输入记录（1 2 100）时：

100, 0, -100, 0, 0, 0

这意味着当您进行最终扫描和汇总时，您的循环将逐步计算

索引 0，总和 100

索引 1，总和 100

索引 2，总和 0

索引 3，总和 0 ...

当获取第二个输入记录（2 5 100）时：

100, 100, -100, 0, 0, -100

这意味着当您进行最终扫描和汇总时，您的循环将逐步计算

索引 0，总和 100

索引 1，总和 200

索引 2，总和 100

索引 3，总和 100

索引 4，总和 100

索引 5，总和 0

所以最大值发生在索引 1 处，

当获取第二个输入记录（3 4 100）时：

100、100、0、0、-100、-100

这意味着当您进行最终扫描和汇总时，您的循环将逐步计算

索引 0，总和 100

索引 1，总和 200

索引 2，总和 200

索引 3，总和 200

索引 4，总和 100

索引 5，总和 0

所以最大值发生在索引 1 处，

推荐阅读