什么是差分数组?

差分数组也是一个数组,只不过它的产生是由原数组进化而来。

首先我们定义一个原数组array长度为8:

INDEX01234567
原数组1253101005466

然后定义一个差分数组tempArray长度也为8,差分数组的每一项取值为(第一项默认为原数组第一项):

tempArray[i] = array[i] - array[i-1] ;(i>0)

INDEX01234567
原数组1253101005466
差分数组113-2790-4612
 //原数组
 int[] array = {1,2,5,3,10,100,54,66};
 System.out.println(Arrays.toString(array));

//差分数组
int[] tempArray = new int[8];
tempArray[0] = array[0];
for (int i = 1 ;i<array.length ;i++){
    tempArray[i] = array[i] - array[i-1];
}
System.out.println(Arrays.toString(tempArray));

差分数组特点

差分数组恢复原数组就是累加即可。

例如原数组:array[2] = tempArray[2]+tempArray[1]+tempArray[0];

5 = 3+1+1;

差分数组的使用案例:

1、区间修改

需求:原数组的第0-5项都加上11。

只需要修改差分数组的第0项和第5项即可。因为差分数组是有后一项减去前一项获得。

即为:第0项+=11,第5项-=11。

然后再还原为原数组即可,获得第0-5都加11的数组。

//需求一,原数组的第0-5都加上11
tempArray[0] +=11;
tempArray[5] -=11;
//打印原数组
for (int i = 1 ;i< tempArray.length ;i++){
    tempArray[i] += tempArray[i-1];
}
System.out.println(Arrays.toString(tempArray));
[1, 2, 5, 3, 10, 100, 54, 66]
[1, 1, 3, -2, 7, 90, -46, 12]
[12, 13, 16, 14, 21, 100, 54, 66]

2、航班预订统计

leetcode上的1109题:https://leetcode-cn.com/problems/corporate-flight-bookings/

这里有 n 个航班,它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ,表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti (包含 firsti 和 lasti )的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer,其中 answer[i] 是航班 i 上预订的座位总数。

输入:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出:[10,55,45,25,25]
解释:
航班编号        1   2   3   4   5
预订记录 1 :   10  10
预订记录 2 :       20  20
预订记录 3 :       25  25  25  25
总座位数:      10  55  45  25  25
因此,answer = [10,55,45,25,25]

使用差分数组解决这个题目思路:

1、原数组为长度为n的数组,初始化值全部为0。

2、差分数组的也是全部为0的数组。

3、bookings数组的长度就是进项区间累加的次数。

2、然后还原原数组即可。

int[] nums = new int[n];
for (int[] booking : bookings) {
    nums[booking[0] - 1] += booking[2];
    if (booking[1] < n) {
        nums[booking[1]] -= booking[2];
    }
}
for (int i = 1; i < n; i++) {
    nums[i] += nums[i - 1];
}
System.out.println(Arrays.toString(nums));
return nums;

效率提升还是很明显的之前写的暴力解法1700多ms,差分数组2ms

文章目录