难度: Medium
原题连接
内容描述
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.
Example:
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]
Explanation:
Initial state:
[0,0,0,0,0]
After applying operation [1,3,2]:
[0,2,2,2,0]
After applying operation [2,4,3]:
[0,2,5,5,3]
After applying operation [0,2,-2]:
[-2,0,3,5,3]
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******
开始无脑写的暴力超时了
class Solution(object):
def getModifiedArray(self, length, updates):
"""
:type length: int
:type updates: List[List[int]]
:rtype: List[int]
"""
res = [0] * length
for idx, update in enumerate(updates):
start, end, inc = update
for i in range(start, end+1):
res[i] += inc
return res
思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******
在思路1的基础上加了一下cache，AC了，但是还是非常慢，beats 4.54%
class Solution(object):
def getModifiedArray(self, length, updates):
"""
:type length: int
:type updates: List[List[int]]
:rtype: List[int]
"""
res = [0] * length
lookup = {}
for idx, update in enumerate(updates):
start, end, inc = update
lookup[(start, end)] = lookup.get((start, end), 0) + inc
for k, v in lookup.items():
start, end = k
for i in range(start, end+1):
res[i] += v
return res思路 3 - 时间复杂度: O(N + len(updates))- 空间复杂度: O(1)******
参考Detailed explanation if you don't understand, especially "put negative inc at [endIndex+1]"
You may see many of the elegant solutions (such as this solution) that puts inc at startIndex and -inc at endIndex + 1,
but it might take you a while to understand why it works, if you are still stuck, read on.
The idea seems tricky at first look but is actually simple after you understand it,
basically we want to achieve the final result array in two passes:
Iterate through the k update operations and "somehow" mark them in the [0, 0, 0, 0, 0] array (using length 5 for example),
for each operation, only update startIndex and endIndex + 1. this is O(k) in total.
iterate through the marked array and "somehow" transforms it to the final result array. this is O(n) in total (n = length).
All in all it is O(n + k).
Now think in a simpler way first, if you have only one update operation, suppose input is (n = 5, updates = { {1, 3, 2} }), what does the O(n + k) solution do?
Initialize the result array as length of n + 1, because we will operate on endIndex + 1:
result = [0, 0, 0, 0, 0, 0]
Then marks index 1 as 2 and marks index 3+1 as -2:
result = [0, 2, 0, 0, -2, 0]
Next, iterate through result, and accumulates previous sum to current position, just like 303. Range Sum Query - Immutable:
result = [0, 0 + 2, 0 + 2, 0 + 2, 2 + (-2), 0] = [0, 2, 2, 2, 0, 0]
Finally, trivial work to discard the last element because we don't need it:
result = [0, 2, 2, 2, 0], which is the final result.
Now you might see why we do "puts inc at startIndex and -inc at endIndex + 1":
Put inc at startIndex allows the inc to be carried to the next index starting from startIndex
when we do the sum accumulation.
Put -inc at endIndex + 1 simply means cancel out the previous carry from the next index of the endIndex,
because the previous carry should not be counted beyond endIndex.
And finally, because each of the update operation is independent and the list operation is just an accumulation of
the "marks" we do, so it can be "makred" all at once first and do the range sum at one time at last step.
beats 88.31%
class Solution(object):
def getModifiedArray(self, length, updates):
"""
:type length: int
:type updates: List[List[int]]
:rtype: List[int]
"""
res = [0] * (length+1)
for start, end, inc in updates:
res[start] += inc
res[end+1] -= inc
for i in range(1, length):
res[i] += res[i-1]
return res[:-1]