class Solution {
public:
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
}
};
370. 区间加法
假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。
其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex ... endIndex]（包括 startIndex 和 endIndex）增加 inc。
请你返回 k 次操作后的数组。
示例:
输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] 输出: [-2,0,3,5,3]
解释:
初始状态: [0,0,0,0,0] 进行了操作 [1,3,2] 后的状态: [0,2,2,2,0] 进行了操作 [2,4,3] 后的状态: [0,2,5,5,3] 进行了操作 [0,2,-2] 后的状态: [-2,0,3,5,3]
相似题目
原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 6.6 MB, 提交时间: 2023-10-16 23:11:22
func getModifiedArray(length int, updates [][]int) []int {
ans := make([]int, length+1)
for i := range updates{
start := updates[i][0]
end := updates[i][1]
inc := updates[i][2]
ans[start] += inc
ans[end+1] -= inc
}
for i:=0; i<length-1; i++{
ans[i+1] = ans[i] + ans[i+1]
}
return ans[:len(ans)-1]
}
java 解法, 执行用时: 1 ms, 内存消耗: 47.7 MB, 提交时间: 2023-10-16 23:10:59
class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
// 定义与原数组对应的差分数组，原数组元素全为0，
// 根据定义，差分数组当然也全初始化为默认值0
int[] d = new int[length];
// 所有更新操作“映射”到差分数组上进行
for(int i=0;i<updates.length;i++) {
int[] u = updates[i];
// 更新左端点
d[u[0]] += u[2];
// 更新右端点的下一个位置
if(u[1] < length-1) {
d[u[1]+1] -= u[2];
}
}
//由差分数组，还原为原数组返回
for(int i=1;i<length;i++) {
d[i] += d[i-1];
}
return d;
}
}
python3 解法, 执行用时: 60 ms, 内存消耗: 22.2 MB, 提交时间: 2023-10-16 23:10:43
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
n = length
################ 典型差分，上下台阶的思想，"出租车上下车问题"
f = [0 for _ in range(n)] #差分数组
#### 差分
for start, end, diff in updates:
f[start] += diff
if end + 1 < n:
f[end + 1] -= diff
#### 整理
for i in range(1, n):
f[i] += f[i-1]
return f
cpp 解法, 执行用时: 28 ms, 内存消耗: 17.8 MB, 提交时间: 2023-10-16 23:10:18
class Solution {
public:
// 暴力
vector<int> getModifiedArray1(int length, vector<vector<int> > updates) {
vector<int> result(length, 0);
for (auto& tuple : updates) {
int start = tuple[0], end = tuple[1], val = tuple[2];
for (int i = start; i <= end; i++) {
result[i] += val;
}
}
return result;
}
// 差分数组
vector<int> getModifiedArray2(int length, vector<vector<int>>& updates) {
vector<int> vec(length,0);
for (auto x:updates){
vec[x[0]]+=x[2];
if (x[1]+1<length) vec[x[1]+1]-=x[2];
}
for (int i=1;i<length;++i) vec[i]+=vec[i-1];
return vec;
}
// 区间求和
vector<int> getModifiedArray(int length, vector<vector<int> > updates) {
vector<int> result(length, 0);
for (auto& tuple : updates) {
int start = tuple[0], end = tuple[1], val = tuple[2];
result[start] += val;
if (end < length - 1)
result[end + 1] -= val;
}
// partial_sum applies the following operation (by default) for the parameters {x[0], x[n], y[0]}:
// y[0] = x[0]
// y[1] = y[0] + x[1]
// y[2] = y[1] + x[2]
// ... ... ...
// y[n] = y[n-1] + x[n]
partial_sum(result.begin(), result.end(), result.begin());
return result;
}
};