? 优质资源分享 ?

差分数组

什么是差分数组？

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

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

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

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

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

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

参考博文：差分数组

差分数组的作用

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

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

编码实现

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

java

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];
}

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

java

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（可以是负数）：

java

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

例子

highlighter- CSS

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

highlighter-

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]

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

txt

0   0   0   0   0
10  10                  
    20  20
    25  25  25  25
--------------------
10  55  45  25  25

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

java

    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

• 采用差分数组，对原数组的某些区间的加操作，全部都注入到差分数组中，最后直接通过差分数组即可得到结果数组。

java

    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)，因为返回值不计入空间复杂度；

• 差分数组

  • 什么是差分数组？
  • 差分数组的作用
  • 编码实现
  • 例子

  __EOF__

  阿飞的客栈# - 本文链接： https://blog.csdn.net/afei688/p/16598099.html

  • 关于博主： 评论和私信会在第一时间回复。或者直接私信我。
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
  • 声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。

转载请注明：xuhss » 差分数组入门