数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学科
时尚研究
法律研究C++中的范围加法
假设我们有一个大小为 n 的数组，该数组初始化为 0，我们还有一个值 k，我们将执行 k 次更新操作。每个操作将表示为三元组： [startIndex, endIndex, inc]，其中 inc 将子数组 A[startIndex ... endIndex]（包括 startIndex 和 endIndex）的每个元素递增。我们必须找出在执行所有 k 次操作后修改后的数组。
因此，如果输入类似于 length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]，那么输出将为 [- 2,0,3,5,3]
为了解决这个问题，我们将遵循以下步骤 -
定义大小为 n 的数组 ret
对于初始化 i := 0，当 i < a 的大小，更新（增加 i 1），操作 -
l := a[i, 0]
r := a[i, 1] + 1
ret[l] := ret[l] + a[i, 2]
如果 r < n，那么 -
ret[r] := ret[r] - a[i, 2]
对于初始化 i := 1，当 i < n，更新（增加 i 1），操作 -
ret[i] := ret[i] + ret[i - 1]
返回 ret
示例
让我们看看以下实现以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto< v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int< getModifiedArray(int n, vector& a) {
vector<int< ret(n);
for (int i = 0; i < a.size(); i++) {
int l = a[i][0];
int r = a[i][1] + 1;
ret[l] += a[i][2];
if (r < n) {
ret[r] -= a[i][2];
}
}
for (int i = 1; i < n; i++) {
ret[i] += ret[i - 1];
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int<> v = {{1,3,2},{2,4,3},{0,2,-2}};
print_vector(ob.getModifiedArray(5,v));
}输入
5, {{1,3,2},{2,4,3},{0,2,-2}}输出
[-2, 0, 3, 5, 3, ]
更新于： 2020 年 11 月 19 日
178 次浏览
广告