差分数组

发表于 更新于 分类于 ，

简介

差分数组是一种对频繁修改区间数据（频繁对一个区间中的每一个元素进行修改）问题的一种优化时间复杂度的操作（空间换时间）。

假如有一个很大的数据a.size = 1e+999，需要多次对一个特定的区间[left,right]中的所有数据加上或减去一个固定的数值。一个通常的做法是进行模拟，依次对a[left]~a[right]中的每一个数据进行增加或删除操作，其时间复杂度为\(O(n*max(right-left))\)，其中\(n\)为操作次数。若采用差分数组，其时间复杂度为\(O(n+l)\)，其中\(n\)为查询次数，\(l\)为差分数组长度。以下为其主要思想。

Method

  • a为初始未进行任何操作的数组；
  • 建立差分数组diff，其尺寸与a一致，diff[0]=a[0];diff[i]=a[i]-a[i-1]，即记录a中相邻元素的差值；
  • 当对a中的区间[left,right]进行一次修改操作时(例如增加x)，仅需diff[left]+=x;diff[right+1]-=x，diff中的其他数据不需要进行变动，因为对整个区间做修改仅仅会影响到边界的差值，其他位置的差值保持不变，每一次修改的时间复杂度为\(O(1)\)；
  • 多次修改操作后需要将差分数组变换成原数组修改后的数组，根据差分数组的性质，直接求差分数组的前缀和即可得到修改后的数组。

简单差分示例：

image-20210723203808006
image-20210723203808006

例子

(取自leetcode1893)

给你一个二维整数数组 ranges 和两个整数 left和 right 。每个ranges[i] = [starti, endi] 表示一个从 starti到endi的 闭区间 。

如果闭区间[left, right]内每个整数都被ranges中 至少一个 区间覆盖，那么请你返回true ，否则返回 false 。

已知区间 ranges[i] = [starti, endi] ，如果整数x 满足starti <= x <= endi ，那么我们称整数x 被覆盖了。

1
2
3
4
5
6
7
8
9
示例 1：

输入：ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
输出：true
解释：2 到 5 的每个整数都被覆盖了：

- 2 被第一个区间覆盖。
- 3 和 4 被第二个区间覆盖。
- 5 被第三个区间覆盖。
1
2
3
4
5
- 示例 2：

输入：ranges = [[1,10],[10,20]], left = 21, right = 21
输出：false
解释：21 没有被任何一个区间覆盖。

此外，题中限定了输入数据的范围：

1
2
3
1 <= ranges.length <= 50
1 <= starti <= endi <= 50
1 <= left <= right <= 50

我们可以据此方便的建立差分数组。

暴力解法

建立一个数组，0代表没有覆盖，1代表有覆盖，遍历ranges中的区间，将a中的可覆盖的索引处都置1，然后遍历a中的[left,right]区间查看是否有0，有则未全覆盖，无则全覆盖。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        a = [0]*52 # 建立数组尺寸稍大，防止越界
        for r in ranges: # 遍历每一个区间
            for i in range(r[0],r[1]+1): # 遍历每一个区间中的每一个索引
                a[i]=1
        for i in range(left,right+1): # 对目标区间进行检查
            if a[i]==0:
                return False
        return True

差分数组解法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        diff = [0]*52 # 建立差分数组
        for r in ranges: # 对差分数组进行修改操作，记录每个索引被区间覆盖的次数
            diff[r[0]] += 1
            diff[r[1]+1] -= 1
        prefix = 0 # 未建立前缀和数组，节约空间
        for i in range(right+1): # 还原每个索引处的覆盖次数
            prefix += diff[i]
            if prefix<=0:
                if i>=left: # 在目标区间中发现覆盖次数小于1（即未被覆盖），直接返回False
                    return False
        return True