差分数组入门

差分数组

什么是差分数组?

差分数组:差分数组就是原始数组相邻元素之间的差。

差分数组入门

其实差分数组是一个辅助数组,从侧面来表示给定某一数组的变化,一般用来对数组进行区间修改的操作。

比如说对于上文的数组,将区间【1,4】的数值全部加上3,其实当原始数组中元素同时加上或者减掉某个数,那么他们的差分数组其实是不会变化的,如下图所示:

差分数组入门

对区间 [1, 4] 的元素都进行加3操作,差分数组中改变的只是 d[1] 和 d[5],而 d[2] d[3] d[4] 都没变。

把上一步得到的数组当成原数组,再将区间【3,5】的数值全部减去5,结果如下:

差分数组入门

总结:当对一数组的某个区间进行增减某个值时,其差分数组对应的区间左端点的值会同步变化,而他的右端点的后一个值则会相反变化。

参考博文:差分数组

差分数组的作用

差分数组的作用就是求多次进行区间修改后的数组。构造出差分数组,就可以快速进行区间增减了。花费O(1)的时间修改 diff 数组,就相当于给原数组的整个区间做了修改。

注意 :只能是区间元素同时增加或减少相同的数的情况才能用。

编码实现

通过原数组求出差分数组:

int[] diff = new int[nums.length]; // 根据原数组构造差分数组 diff[0] = nums[0]; for(int i = 1; i < nums.length; ++i) {     diff[i] = nums[i] - nums[i - 1]; } 

通过差分数组得到结果数组:

int[] res = new int[diff.length]; // 通过差分数组得到结果数组 res[0] = diff[0]; for(int i = 1; i < diff.length; ++i) {     res[i] = res[i - 1] + diff[i]; } return res;  //-------------其实直接在diff上操作即可得到结果数组---------------- for(int i = 1; i < diff.length; ++i) {     diff[i] += diff[i - 1]; } return diff; 

给区间 [i, j] 增加 val(可以是负数):

// 直接操作 diff diff[i] += val; if(j + 1 < diff.length) {     diff[j + 1] -= val; } 

例子

lc-1109. 航班预订统计 *  给你输⼊⼀个⻓度为 n 的数组 nums,其中所有元素都是 0。再给你输⼊⼀个 bookings,⾥⾯是若⼲三元组(i,j,k), *  每个三元组的含义就是要求你给 nums 数组的闭区间 [i-1,j-1] 中所有元素都加上 k。请你返 回最后的 nums 数组是多少? 
输入:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 输出:[10,55,45,25,25] 

这个例子初始的原数组全为0,表示 n 个航班初始预定的座位数都为0。对原数组的某些区间有多次加操作,过程如下:

0	0	0	0	0 10	10					 	20	20 	25	25	25	25 -------------------- 10  55  45  25  25 
  • 若采用常规思路,则通过二重循环可以得到结果数组,外循环遍历每个booking,内循环对每个booking中的区间进行遍历,区间内的值加上座位数,外循环结束,即可得到结果数组。但该解法最坏情况下时间复杂度为O(m*n);

        public int[] corpFlightBookings(int[][] bookings, int n) {         int[] ans = new int[n];         for(int[] nums : bookings) {             for(int i = nums[0]; i <= nums[1]; i++) {                 ans[i - 1] += nums[2];             }         }         return ans;     }  执行用时: 1568 ms 内存消耗: 55.3 MB 
  • 采用差分数组,对原数组的某些区间的加操作,全部都注入到差分数组中,最后直接通过差分数组即可得到结果数组。

        public int[] corpFlightBookings(int[][] bookings, int n) {         // 初始化差分数组(因为原数组初始全为0)         int[] diff = new int[n];         // 遍历二维数组中的每一行         for (int[] b : bookings) {             // 把每一行的值赋给i、j、val。数组下标从0开始,而题中是从1开始,为了对应要-1             int i = b[0] - 1, j = b[1] - 1, val = b[2];             // 差分数组左边界加val(原数组中相当于i后面所有数都加了val)             diff[i] += val;             // 隔断右边界,把j+1后的所有值减去val,上一步加,这一步减,相当于j+1后的值原数组中没变             if(j + 1 < n)                 diff[j + 1] -= val;         }          // 上面循环结束,得到的diff就是差分数组,根据差分数组构造结果数组         int[] res = new int[n];         res[0] = diff[0];         for (int i = 1; i < n; i++) {             // 得到结果数组中的每个值             res[i] = res[i - 1] + diff[i];         }         return res;     }  执行用时: 2 ms 内存消耗: 55.7 MB /* 差分数组变化: 	0		0		0		0		0 	10		0		-10		0		0	// 0 和 1下标加10 	10		20		-10		-20		0	// 1 和 2下标加20 	10		45		-10		-20		0	// 1 ~ 4下标加25	 */ 

    时间复杂度:O(m + n),m 为预定记录的数量,n 为数组长度;

    空间复杂度:O(n),申请的差分数组diff占用的空间,其实可以不用申请res,直接把diff当作返回数组,这样空间可以降到O(1),因为返回值不计入空间复杂度;

发表评论

相关文章