数组操作hackerrank解决方案python

hi3rlvi2  于 2023-05-02  发布在  Python
关注(0)|答案(2)|浏览(116)

我正在解决HackerRank问题Array Manipulation
从一个索引为1的零数组和一个操作列表开始,对于每个操作,将一个值添加到两个给定索引之间的每个数组元素中。执行完所有操作后,返回数组中的最大值。
我的代码在大多数情况下都能正常工作,但是当nm是巨大的数字时,我在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()

我尝试打印一些细节,但它不显示在调试输出

lp0sw83n

lp0sw83n1#

你的代码必须执行的更新数量太大了(至少对于Python来说)。
相反,您可以将查询拆分为启动和停止事件,然后对这些事件进行排序。最后迭代这些事件以获得最大累积值。

from itertools import accumulate
 
def arrayManipulation(n, queries):
    return max(accumulate(value for _, value in 
             sorted([(first, value) for first, _, value in queries]
                  + [(last + 1, -value) for _, last, value in queries])
    ))
k4ymrczo

k4ymrczo2#

C++足够快,你可以摆脱低效。Python更慢,这个算法不再足够好。
不是将数据存储在值数组中,而是存储在增量数组中。有很多方法可以做到这一点。假设你的数组看起来像这样:

A = [a0, a1, a2, a3, a4, a5, a6, a7, a8, a9]

将其转换为对ai-aj,其中j是第一个可被2的更高次幂整除的前一个数字。就像这样

B = [a0, a1-a0, a2-a0, a3-a2, a4-a0, a5-a4, a6-a4, a7-a6, a8-a0, a9-a8]
  = [b0,    b1,    b2,    b3,    b4,    b5,    b6,    b7,    b8,    b9]

您可以通过更高幂的伸缩和将B转换回A

A = [b0, b0+b1, b0+b2, b0+b2+b3, b0+b4, b0+b4+b5, b0+b4+b6, b0+b4+b6+b7, b0+b8, b0+b8+b9]
  = [a0, a0+b1, a0+b2,    a2+b3, a0+b4,    a4+b5,    a4+b6,       a6+b7, a0+b8,    a8+b9]

我们可以使用O(n)工作在这些之间来回转换。
但是假设我们得到一个查询[i, j, k]。在A表示中,这需要O(j-i+1)工作。在B表示中,这最多需要O(log(n))工作。(从i开始,不断将+k与2的递增幂相加,直到达到j。然后将-k添加到2的递增幂中,直到达到范围内2的最高幂的两倍。)
你得小心把索引做好。但是对于范围很大的大量查询,这是一个相当大的性能差异。

相关问题