特定范围内数组中每个元素的增量值

Question

有一个包含 n 个元素的数组 A[]。还有另一个大小为 n 的数组 B[]，每个元素都初始化为零。对于1到n范围内的每个i，B[]在i-A_i到i+A_i（含）范围内的元素需要增加1.

我已经尝试过使用嵌套循环方法的 O(n^2) 解决方案。如果存在，我真的无法找出 O(n) 解决方案。

i=1;
while(i<=n)
{
start=(i-A[i]<1)?1:i-A[i];
end=(i+A[i]>n)?n:i+A[i];
while(start<=end)
{
B[start]+=1;
start+=1;
}
i+=1;
}

Answer 1

一个天真的实现是增加 A 中每个项目的每个范围，但你不需要这样做。您可以首先 "prepare" 您的数组，方法是在增量应开始的位置添加 1，在增量应停止的位置添加 -1。接下来，您可以计算数组的 cummulative 总和。喜欢：

def fill_list(la):
    lb = [0]*len(la)
    n1 = len(la)-1
    for i, a in enumerate(la, 1):
        xf, xt = i-a, i+a+1
        lb[max(0, i-a)] += 1
        if xt <= n1:
            lb[xt] -= 1
    c = 0
    for i, b in enumerate(lb):
        c += b
        lb[i] = c
    return lb

或者如果你想 return 范围从 1 到 n:

def fill_list1(la):
    n1 = len(la)
    lb = [0]*(n1+1)
    for i, a in enumerate(la, 1):
        xf, xt = i-a, i+a+1
        lb[max(0, i-a)] += 1
        if xt <= n1:
            lb[xt] -= 1
    c = 0
    for i, b in enumerate(lb):
        c += b
        lb[i] = c
    return lb[1:]

然后我们可以生成一个列表：

>>> fill_list([1,4,2,5,1,3,0,2])
[4, 4, 4, 5, 5, 5, 4, 3]
>>> fill_list1([1,2,3,4,5])
[5, 5, 4, 4, 3]

因此范围为：

 -3 -2 -1  0  1  2  3  4  5  6  7  8  9 10 11
--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--
           |-----|
     |-----------------------|
              |-----------|
        |-----------------------------|
                       |-----|
                    |-----------------|
                                |
                             |-----------|
--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--
  0  1  1  1  1  0  0  1  0  0 -1 -1 -1 -2 -1
--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--
  0  1  2  3  4  4  4  5  5  5  4  3  3  1  0

在范围开始之前完成的增量（因此索引小于 0）仅放置在索引 0 处，以便我们将这些考虑在内。在 window 之后完成的那些（因此索引大于或等于 n 将被忽略）。

在图像中，第一行显示索引，接下来我们表示来自相同输入的范围，接下来我们显示将放在无限磁带上的增量和减量，接下来我们显示累积和.

算法工作在O(n)：首先我们在线性时间内迭代la，并对b中的相应元素进行递增和递减.接下来我们迭代 b，再次在 O(n) 中计算累积和。

特定范围内数组中每个元素的增量值

Increment value of every element in an array in a particular range

arrays

logic

loops

increment

time-complexity