python - 数组操作 | Hackerrank 运行时错误问题

Question

我正在从hackerrank做这个数组操作问题，它告诉我运行时错误。从我的角度来看，时间复杂度是 O(n)。但它仍然遇到了这个问题。任何人都可以帮助我吗？

以下是链接：

从 1 索引的零数组和操作列表开始，为每个操作添加一个值到两个给定索引之间的每个数组元素，包括两个给定索引。执行完所有操作后，返回数组中的最大值。

例如，您的 zeros 数组的长度。您的查询列表如下：

a b k
1 5 3
4 8 7
6 9 1

在索引和包容之间添加 的值：

index -> 1 2 3  4  5 6 7 8 9 10
        [0,0,0, 0, 0,0,0,0,0, 0]
        [3,3,3, 3, 3,0,0,0,0, 0]
        [3,3,3,10,10,7,7,7,0, 0]
        [3,3,3,10,10,8,8,8,1, 0]

最大值是在执行了所有操作之后。

我在这里附上了我的代码：

def arrayManipulation(n,queries):
    increment=[]
    value=[]
    for i in range(n):
        increment+=[0]
        value+=[0]
    for j in range(m):
        left=queries[j][0]
        right=queries[j][1]
        k=queries[j][2]
        increment[left-1]+=k
        if right>=n:
            continue
        else:
            increment[right]-=k
    value[0]=increment[0]
    for i in range(1,n):
        value[i]=value[i-1]+increment[i]
    maximum=max(value)
    return maximum

标签： pythonarrayspython-3.x

Answer 1

如果您只是在正确的索引处添加/减去，您可以简化这个问题 - 所以您只有 2 个操作而不是 2000 个操作

1 2000 3 

您的查询列表如下：

a b k
1 5 3
4 8 7
6 9 1


# demonstation purposes, do not create list with 200k zero entries - use a dict. see below.
[+3, 0, 0,  0, -3,  0, 0,  0, 0, 0]     # 2 index ops by 1 5 3
[+3, 0, 0, +7, -3,  0, 0, -7, 0, 0]      # 2 index ops by 4 8 7
[+3, 0, 0, +7, -3, +1, 0, -7,-1, 0]     # 2 index ops by 6 9 1

# sums:
  3  3  3  10   7   8  8   1  0  0  # for loop through list, adding all, remembering max

您可以通过一次通过整个列表来获得最大值，然后在通过时简单地将所有数字相加 + 记住最大值。

这简化了破坏内存/计算时间的大型列表的整个问题。

而不是这样做（对于 200k 长列表）

 1 2000 3  # 2000 times change value
11 2000 3  # 2000 times change value
21 2000 3  # 2000 times change value 
31 2000 3  # 2000 times change value
41 2000 3  # 2000 times change value

你做了 10 次价值改变：

# demonstation purposes, do not create list with 200k zero entries - use a dict. see below.
[ ..., +3, ..., +3, ..., +3, ..., +3, ..., +3, ............, 
       -3, ..., -3, ..., -3, ..., -3, ..., -3, ...] 

{1:3, 11:3, 21:3, 31:3, 41:3, 2001:-3, 2011:-3, 2021:-3, 2031:-3, 2041:-3}

并在按键排序并添加您得到的值时：

 3, 6, 9, 12, 15, 18, 15, 13, 12, 9, 6, 3 

您应该能够将这些内容插入到带有 key == position 的 dict 中（如果多次出现，请确保更新键的值而不是替换它：

3 7 3
3 9 3
3 5 3

{3:9,7:-3, 9:-3, 5:-3} # 3 updated several times 

---

弄清楚这些想法使一些hackerranks变得有趣（尽管很多只是不好/不清楚）。

这是代码，玩得开心-复制和粘贴解决方案并不是什么成就-这就是为什么我一开始没有编写代码的原因...

maxElem, inputs = [int(n) for n in input().split(" ")]
d = {}
for _ in range(inputs):
    x, y, incr = [int(n) for n in input().split(" ")]
    d.setdefault(x,0)
    d[x]=d[x]+incr 
    if(y <= maxElem+2):
        d.setdefault(y+1,0)
        d[y+1]=d[y+1]-incr

maxx = 0
x= 0 

for i in sorted(d): 
    x+=d[i]
    if(maxx<x): 
        maxx=x

print(maxx)