0%

【前缀和】差分数组的使用

今天的每日一题,1109. 航班预订统计
看完描述,这算什么中等题,我直接开干。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] answer = new int[n];
for(int i = 1; i <= n; i++){
for(int j = 0; j < bookings.length; j++){
if(i>= bookings[j][0] && i <= bookings[j][1]){
answer[i-1] += bookings[j][2];
}
}
}
return answer;
}
}

时间复杂度O(m*n),果不其然,一个时的超

然后稍微优化了一下

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] answer = new int[n];
for(int i = 0; i < bookings.length; i++){
for(int j = bookings[i][0]; j <= bookings[i][1]; j++){
answer[j-1] += bookings[i][2];
}
}
return answer;
}
}

这次的代码本质上也是O(m*n)的复杂度,不过比之前的小很多,还好过了,耗时1631ms,击败了9%的小伙伴。

怎会如此.jpg,就这么一个看起来普普通通的题还能玩出花来?看看题解怎么说。

看完题解,我是伞兵,前缀和还能这么用的吗?
根据bookings这个数组可以得到每个航班预定座位的改变值。
再次大受震撼.jpg
我连续看了两次
看完动弹不得

放代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
// d[] 用来记录改变值
int[] d = new int[n+1];
int[] answer = new int[n];

for(int i = 0; i < bookings.length; i++){
d[bookings[i][0]-1] += bookings[i][2];
d[bookings[i][1]] -= bookings[i][2];
}
answer[0] = d[0];
for( int i = 1; i < n; i++){
answer[i] += d[i]+answer[i-1];
}
return answer;
}
}

O(m*n)的算法就像一条一条,有条不紊的整理好每一条记录
而题解这个O(m+n)的算法,就像一巴掌把所有记录拍在一起,但结果没有问题Orz