0

我正在做一个问题。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]

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

4

2 回答 2

3

在这个问题的讨论页面中，有一个 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 处，

于 2018-09-16T14:00:15.763 回答
2

我的回答仅针对您问题的算法部分，我将简化 i/o 而不是将其实现为函数，以留下一些东西来测试您的技能。

这个想法是，不要存储结果，而是存储每个位置的累积增量，然后通过累积求和找到最大值。

让我们看看问题陈述中报告的第一个示例，

10 3
1 5 3
4 8 7
6 9 1

我们从 开始l，一个长度等于的零列表n+1（为什么是n+1？因为我们需要一点额外的空间来存储delta时b==n）；我们只想存储l在delta的

n, m = 10, 3
l = [0]*(n+1)

我们对 3 个查询重复相同的操作，并l在评论中报告我们列表的状态

a, b, k = 1, 5, 3
l[a-1] += k ; l[b] -= k
# [0, 0, 3, 0, 0, -3, 0, 0, 0, 0, 0]

a, b, k = 4, 8, 7
l[a-1] += k ; l[b] -= k
# [0, 0, 3, 7, 0, -3, 0, 0, -7, 0, 0]

a, b, k = 6, 9, 1
l[a-1] += k ; l[b] -= k
# [0, 0, 3, 7, 1, -3, 0, 0, -7, -1, 0]

current_max = 0
current_sum = 0
debug = 1
for num in l[:-1]:
    current_sum += num
    if debug: print(current_sum)
    current_max = max(current_max, current_sum)

print(current_max)

执行上面的代码给了我

3
3
3
10
10
8
8
8
1
0
10

前十个数字是求和列表的元素，要与问题陈述进行比较，最后一个数字是要求的最大值

于 2018-09-16T15:05:06.863 回答