算法数据结构----差分数组
什么是差分数组?
差分数组也是一个数组,只不过它的产生是由原数组进化而来。
首先我们定义一个原数组array长度为8:
INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
原数组 | 1 | 2 | 5 | 3 | 10 | 100 | 54 | 66 |
然后定义一个差分数组tempArray长度也为8,差分数组的每一项取值为(第一项默认为原数组第一项):
tempArray[i] = array[i] - array[i-1] ;(i>0)
INDEX | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
原数组 | 1 | 2 | 5 | 3 | 10 | 100 | 54 | 66 |
差分数组 | 1 | 1 | 3 | -2 | 7 | 90 | -46 | 12 |
//原数组
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
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
整挺好