基本思想:
差分法的主要是用于处理区间问题。当要对不同区间的元素进行统一 *** 作时,为了避免多重循环引起的高复杂度,使用差分法,通过首先对区间端点元素进行 *** 作,再通过前缀求和(当前位置元素=上一个位置元素+当前位置变化)的方式来得到一个新的数组,完成 *** 作。
1109.航班预定统计
public int[] corpFlightBookings(int[][] bookings, int n) {
// -------差分法求解------
// 可以将问题转换为:求解公交车上每一站的人数
// int[] res = new int[n];
// count记录每一站的人数变化情况
int[] count = new int[n];
for (int[] booking : bookings) {
// 乘客上车,代表在初始站预定车票
count[booking[0] - 1] += booking[2];
// 乘客下车, 代表在第last+1站不再预定
if (booking[1] < n) {
count[booking[1]] -= booking[2];
}
}
// count开始只记录了乘客上下车的站点情况,
// 那么每一站公交车上人数等于上一站的人数加上本站人数变化情况
for (int i = 1; i < n; i++) {
count[i] += count[i - 1];
}
return count;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)