数据结构与算法-差分数组及应用

差分数组

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

频繁操作数组区间的问题

假设我们要对一个数组进行区间操作。数组为 a = {10,10, 20,20,50,… 100}。数组数据比较多。

1. 对数组的1~3项做加5操作（数组从0开始)

   遍历数组第1项~5项： a = {10,15,25,25,50,…}

2. 对数组2~4项做加3操作

   遍历数组第2~4项： a = {10, 15, 28,28, 53,…}

   。。。。。。。。。。。。。。。。

我们发现大量的频繁的区间内操作每次都要对数据的指定位置进行遍历及运算，这样如果数组过大操作过于频繁会造成数组的响应时间过长，时间复杂度升高。

使用差分数组优化操作

创建差分数组

所谓差分数组即数组中的每一项（除第0项）减去其前一项构成一个新的数组，此数组为差分数组。

在某个区间进行操作

先对区间[1,3]进行+5操作，我们发现差分数组diff[2] = 0, diff[3] = 10; diff[1] = 10+15(即区间的开始位置),diff[4]=30-5(即区间末尾+1)。

在对区间[2,4] 进行+8操作， 我们发现差分数组diff[3]=10, diff[4] = 25，diff[2]=0+8(区间起始位置2)，diff[5]= 10-2=8(区间末尾加1)

差分数组特性

特性1: 给区间[m, n]进行K数据操作

由图我们可以看出每次查分数组 a[start, end] 的操作数组, 从 m+1~n 数据不会发生变化，变化的只是a[m]和a[n+1]位置,且m位置值为原a[m]+K, a[n+1]-K, K值是区间内的每个数组元素的操作数据。

对a[m]+K，则对应的需要 a[n+1]-K

也就是说在差分数组中只有第m项和第n+1项的数据会发生变化(前提： 需要在区间内操作的数据相同)。

特性2： 原数组的每个数据值和差分数组的关系

a[n] = diff(Sum(n-1)) + diff[n]; 原数组当前数据 = 差分数组前项和+ 差分数组当前项

a[1] = diff[0] + diff[1] = diff(Sum(0))+diff[1]= 0 + 15 = 15 = a[0] + diff[1];

a[2] = diff[0] + diff[1] + diff[2] =diff(Sum(1))+diff[2]= 0 + 15+8 = 23 = a[1] + diff[2];

a[3] = diff(Sum(2)) + diff[3] = 23 + 10 = a[2] + diff[3];

:

a[n] = diff(Sum(n-1)) + diff[n] = a[n-1] + diff[n]

差分数组使用

定义一个初始数组：int[] source = {0, 0, 0, 0, 0, 0, 0};

获取差分数组

定义差分数组: int[] diff = new int[source.length];

public static void diffExecute(int[] diff, int[] source) {
    for (int i = 1; i < source.length; i++) {
        diff[i] = source[i] - source[i - 1];
    }
}
1
2
3
4
5

区间[1,2]+10操作

在区间[1,2]中每一个数据+10，原数组变化为：

  for (int i = 1; i <= 2; i++) source[i] += 10;
1

差分数组根据性质1： 只有[m,n]m位置和n+1位置会有数据改动。重构差分数组

public static void diffx(int[] diff, int m, int n, int k) {
    diff[m] += k;  //区间起始点
    if (n < diff.length - 1) {
        diff[n + 1] -= k; //区间终止点的下一个位置
    }
}
1
2
3
4
5
6

区间[2,3]做+20操作

在区间[2,3]中每一个数据+20，原数组变化为：

  for (int i = 1; i <= 2; i++) source[i] += 20;
1

差分数组变化,

区间[2,5]做+25操作

在区间[2,3]中每一个数据+25，原数组变化为：

  for (int i = 2; i <=5; i++) source[i] += 25;
1

差分数组变化

由差分数组还原原数组计算后结果

原数组经过了[1,2]区间+10，[2,3]区间+20和[2,5]区间+25操作；我们同时也记录了差分数组的变化结果。接下来使用差分数组反推原数组的结果。此处我们使用差分数组的第2个特性： 当前项=前项和+当前项, diff[i] = diff[i-1] +diff[i]; 为程序清晰，我定义sum来记录前项和(可以自行简化代码)。

int sum = diff[0];
for (int i = 1; i < dest.length; i++) {
    sum = sum + diff[i];
    diff[i] = sum;
}
1
2
3
4
5

我们对比一下原始数据经过一系列变化后，发现和最后的结果是一致的。

经典问题

1109. 航班预订统计 - 力扣（LeetCode）

解题思路使用差分数组

由于在某个区间内会频繁进行数据的操作，可以创建一个差分辅助数组利用性质2，只操作m项和n+1项(m,为区间起始位置，n为区间终止位置的下一个位置)。

public int[] corpFlightBookings(int[][] bookings, int n) {
    int[] diff = new int[n];

    for (int i = 0; i < bookings.length; i++) {  //遍历二维数组找到区间和要修改的值
        int[] booking = bookings[i];
        int val = booking[2];
        int start = booking[0];
        int end = booking[1];
        
        diff[start - 1] += val; //start-1是日期从1开始，我们的数组从0开始,利用差分数组性质1:记录起始位置增量

        if (end < n) {
            diff[end] -= val;   //性质1: 和起始位置进行相反操作，不用+1是因为起始位置左移了一个位置。
        }
    }

    /*
     *  差分数组性质2：  前项和+当前项
     */
    for (int i = 1; i < diff.length; i++) { 
        diff[i] = diff[i] + diff[i - 1];
    }

    return diff;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26