首先就是暴力解法
很耿直的题目
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] res = new int[n];
for(int i = 0; i < bookings.length; ++i){
for(int j = bookings[i][0]; j <= bookings[i][1]; ++j){
res[j-1] += bookings[i][2];
}
}
return res;
}
}
耿直的解法往往就是时间复杂度比较高
上述的时间复杂度就是 n*m
n为预定表的长度
m为航班的趟次
然后就是用差分法
差分法的这个原理呢，也比较好理解
下面就来解释下差分法
nums为原始数组
diff为差分数组
diff[i] = nums[i] - nums[i-1]
反推出来原始数组
res[i] = res[i-1] + diff[i]
对于上述的diff数组来进行反推
res[1] = res[0] + diff[1] = 8-6=2
res[2] = res[1] + diff[2] = 2+4=6
res[3] = res[2] + diff[3] = 6-3=3
res[4] = res[3] + diff[4] = 3-2=1
假如要对原始nums数组进行操作 nums[i,j]进行+3操作，求整体操作之后数组的和
那么仅需要对diff[i] += 3
然后再对diff[j+1] -= 3 进行操作，最后再反推数组即可
对nums[1,3] + 3操作，对于上述diff数组来进行反推可以得到res数组为
res[1] = res[0] + diff[1] = 8-3=5
res[2] = res[1] + diff[2] = 5+4=9
res[3] = res[2] + diff[3] = 9-3=6
res[4] = res[3] + diff[4] = 6-5=1
我们可以观察得到反推过后的res[1,3]确实对比原先的res数组的[1,3]区间上进行了+3的操作
来仔细理解下这个操作
如果在diff数组上进行操作，起始的位置为1，那么diff[1]的地方值+3，那么过后每次进行反推的时候，res[1...]的数组都+3，反推逻辑没变，只是起始位置的值变大了，所以之后的每个元素的值都会变大。因为我们是需要在一个闭区间上面进行加减操作，所以在起始位置上+3之后，需要在结尾的地方将其复原，所以需要在j+1的地方-3，这样才能使j+1之后的元素还原。
下面就用差分法来解这一题
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] diff = new int[n];
int[] res = new int[n];
for(int i = 0; i < bookings.length; ++i){
diff[bookings[i][0]-1] += bookings[i][2];
if(bookings[i][1] < n){
diff[bookings[i][1]] -= bookings[i][2];
}
}
res[0] = diff[0];
for(int i = 1; i < n; ++i){
res[i] = res[i-1] + diff[i];
}
return res;
}
}
var corpFlightBookings = function (bookings, n) {
var nums = new Array(n).fill(0)
for (b of bookings) {
nums[b[0] - 1] += b[2]
if (b[1] < n) {
nums[b[1]] -= b[2]
}
}
for (let i = 1; i < n; ++i) {
nums[i] += nums[i - 1]
}
return nums
}
其实上面对于差分数组的解释已经十分详细了，这一题直接用到了上面的方法
只是有一个地方需要注意，就是临界的问题
比如说航班有5个，那么当我们需要在[2,5]的航班上进行操作的时候
数组的起始为0，其实我们是在diff[1,4]上进行操作，数组长为5
那么我们需要在起始1的地方进行+的操作，然后在结尾4+1的地方进行-的操作
因为数组整体 长度为5，那么我们在结尾4+1的地方进行操作就会越界，所以此时需要判断下
仔细理解下[1,4]上进行操作，那么就是从1开始的地方操作到结尾，所以此时不需要对结尾的地方进行操作
