Range Addition

Posted on | Edited on | In | | Views:

370. Range Addition

Assume you have an array of length n initialized with all 0’s and are given k update operations.
Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.
Return the modified array after all k operations were executed.

给一个length, 这是要返回的数组的长度, 初始的时候所有值为0. 还有一个n*3的数组, 每一行有3个数, 分别代表了start, end和inc. 我们需要更新我们的结果数组, 从start 到 end.

例子:

length = 5,
updates = [
    [1,  3,  2],
    [2,  4,  3],
    [0,  2, -2]
]
  1. 初始化 [0, 0, 0, 0, 0]
  2. 更新 [1, 3], [0, 2, 2, 2, 0]
  3. 更新 [2, 4], [0, 2, 5, 5, 3]
  4. 更新 [0, 2], [-2, 0, 3, 5, 3]

思路

这道题的直观写法很容以做. 就像上面的例子说的那样, 没去都去更新所有. 但是, 这样太慢了, 这样做的时间复杂度是 $O(n \cdot k)$. 根据solution的提示, 有一个时间复杂度为 $O(n + k)$ 的方法. 那就是每次只更新 start 和 end + 1 (如果在范围内的话). res[start] += inc和res[end+1] **-=** inc. 但更新都做完之后, 把res进行累加.就是要返回的结果.

还是用回上面的例子

  1. 初始化 [0, 0, 0, 0, 0]
  2. 更新 1, 4 得到 [0, 2, 0, 0, -2]
  3. 更新 2. 因为5不再范围内. 得到 [0, 2, 3, 0, -2]
  4. 更新 0, 3. 得到 [-2, 2, 3, 2, -2]
  5. 更新整个结果
    • [-2, 2, 3, 2, -2]
    • [-2, 0, 3, 2, -2]
    • [-2, 0, 3, 2, -2]
    • [-2, 0, 3, 5, -2]
    • [-2, 0, 3, 5, 3]

Code

  1. Naive Method

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def getModifiedArray(length, updates):
        res = [0] * length
            
        for update in updates:
            start = update[0]
            end = update[1]
            inc = update[2]
            for i in range(start, end+1):
                res[i] += inc
        return res

  2. Advanced Method

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def getModifiedArray(length, updates):
        res = [0] * length
        for update in updates:
            start = update[0]
            end = update[1]
            inc = update[2]
            res[start] += inc
            if end + 1 < len(res):
                res[end + 1] -= inc
        s = 0
        for i in range(len(res)):
            s += res[i]
            res[i] = s
        return res

时间复杂度

Method 1: $O(n \cdot k)$
Method 2: $O(n + k)$