我正在解决HackerRank问题Array Manipulation:
从一个索引为1的零数组和一个操作列表开始,对于每个操作,将一个值添加到两个给定索引之间的每个数组元素中。执行完所有操作后,返回数组中的最大值。
我的代码在大多数情况下都能正常工作,但是当n
和m
是巨大的数字时,我在HackerRank中得到了一个运行时错误,我不知道为什么。
注:在C++中实现的相同逻辑工作并已被接受。
#!/bin/python3
import math
import os
import random
import re
import sys
import logging
print("hello")
#
# Complete the 'arrayManipulation' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts following parameters:
# 1. INTEGER n
# 2. 2D_INTEGER_ARRAY queries
#
def arrayManipulation(n, queries):
s = [0] * (n+7)
for query in queries :
s[query[0]] += query[2]
s[query[1]+1] += -1 * query[2]
for i in range(1,n+1):
s[i] += s[i-1]
max = -1;
for i in range(n+1):
if(s[i] > max):
max = s[i];
return max
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nm = input().split()
n = int(nm[0])
m = int(nm[1])
queries = []
for _ in range(m):
queries.append(list(map(int, input().rstrip().split())))
result = arrayManipulation(n, queries)
fptr.write(str(result) + '\n')
fpt`r.close()
我尝试打印一些细节,但它不显示在调试输出
2条答案
按热度按时间lp0sw83n1#
你的代码必须执行的更新数量太大了(至少对于Python来说)。
相反,您可以将查询拆分为启动和停止事件,然后对这些事件进行排序。最后迭代这些事件以获得最大累积值。
k4ymrczo2#
C++足够快,你可以摆脱低效。Python更慢,这个算法不再足够好。
不是将数据存储在值数组中,而是存储在增量数组中。有很多方法可以做到这一点。假设你的数组看起来像这样:
将其转换为对
ai-aj
,其中j
是第一个可被2的更高次幂整除的前一个数字。就像这样您可以通过更高幂的伸缩和将
B
转换回A
。我们可以使用
O(n)
工作在这些之间来回转换。但是假设我们得到一个查询
[i, j, k]
。在A
表示中,这需要O(j-i+1)
工作。在B
表示中,这最多需要O(log(n))
工作。(从i
开始,不断将+k
与2的递增幂相加,直到达到j
。然后将-k
添加到2
的递增幂中,直到达到范围内2的最高幂的两倍。)你得小心把索引做好。但是对于范围很大的大量查询,这是一个相当大的性能差异。