LC370. 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.
Example:
Given:
length = 5,
updates = [
[1, 3, 2],
[2, 4, 3],
[0, 2, -2]
]
Output:
[-2, 0, 3, 5, 3]
对于[start, end, inc], 从start到end(inclusive), 的每个item增加inc。
Naive solution:
naive, 607ms. O(nk).
public class Solution {
int[] range;
int length;
public int[] getModifiedArray(int length, int[][] updates) {
this.length = length;
range = new int[length];
for(int[] update: updates){
for(int i = update[0]; i <= update[1]; i++){
range[i] += update[2];
}
}
return range;
}
}
O(n + k) Solution:
思路是对每个update[start, end, inc], range[start] + inc, range[end + 1] - inc. 然后遍历range，这时range里的每个元素记录了从这个元素起始应该增加的值。
public class Solution {
// add update to the begin and -update to the end
// then go through array, add sum to each number
public int[] getModifiedArray(int length, int[][] updates) {
int[] range = new int[length];
for(int[] update: updates){
range[update[0]] += update[2];
if(update[1] < length - 1) range[update[1] + 1] -= update[2];
} // for update
int sum = 0;
for(int i = 0; i < length; i++) {
sum += range[i];
range[i] = sum;
} // for i
return range;
}
}