今天做leetcode 1109 .航班预约统计算法问题的时候,发现可以用差分配列来解决问题。 在调查理解后,将其简单总结,希望今后能合理运用
差值分配数组是指数组中每个项目的值减去上一个项目的值之间的差值后的数组
例如与排列[2、4、3、6、8]对应差分配列为[0、2、-1、3、2]
设b[i]=a[i 1]-a[i],则可以通过一次遍历(for循环)求出
差分配列用作辅助数组,一般用于数组内区间元素加或减相同数值的情况
原排列区间[n,m]的所有要素加3,则差分配列的n项加3(c[n]=3)和m 1项减3 )3(c[m 1]-=3) )。
即,在原始排列[n,m]区间中添加num
差分配列c中,c[n]=c[n] num,c[m 1]=c[m 1] num,其余项不变
代码:
wile(m---- )
cinleftrightchange;
c[left] =change;
c[right 1] -=change;
}
计算结束后,用差分配列恢复原数组a
a[i]=a[i-1] c[i]
for循环一次即可(注意i=0时的特殊情况,包括a[0]=c[0] ) ) ) ) ) ) ) ) ) ) )。
根据这个性质,要计算数组区间内的要素的等价加减,在其差分配列中只计算区间左右两端的值的变化,可以将(m-n )次的数据变化减少到2次,计算变得容易。