差分数组
如果两个信息“长得很像”,只要保留一个,对另一个,只要保留它们的差异,然后进行微调就行了。
差分数组:
- 3210,3208,3206,3211,3220,3212……
- 3210 【-2】【-2】【5】【9】【-8】……
适用场景,频繁对某个区间的元素进行增减。
// 初始化差分数组
diff[0] = nums[0]; // 以第一个值为基础
for (int i = 1; i < nums.length; i++)
diff[i] = nums[i] - nums[i - 1]; // 存储差分值
对区间 nums[i…j] 的元素全部加 5:
- diff[i] += 5
- diff[j+1] -= 5(记得j+1是不需要的)
对区间 nums[i…j] 的元素全部减 5:
- diff[i] += -5(减 5 以加 -5 的方式)
- diff[j+1] -= -5(记得j+1是不需要的)
// 修改差分数组
void add(int l, int r, int c) {
diff[l] += c;
if( r+1 < diff.length )
diff[r+1] -= c;
}
对比常规,给一个区间 [l,r] 上的数组加一个常数c, [l,r] 每个元素都要依次加上c,这样的时间复杂度是 O(n) 的。
而差分数组只修改头、尾,O(1) 的时间。
文章来源:https://www.toymoban.com/news/detail-431871.html
二维差分
这个人写得好:https://blog.csdn.net/m0_74215326/article/details/129620912文章来源地址https://www.toymoban.com/news/detail-431871.html
到了这里,关于差分数组 & 技巧小记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!