1109 - 航班预订统计
# 📃 题目描述
题目链接:1109. 航班预订统计 (opens new window)
# 🔔 解题思路
换一种思路理解题意,将问题转换为:某公交车共有 n 站,第 i 条记录 bookings[i] = [i, j, k] 表示在 i 站上车 k 人,乘坐到 j 站,在 j+1 站下车,需要按照车站顺序返回每一站车上的人数
根据 1 的思路,定义 counter[] 数组记录每站的人数变化,counter[i] 表示第 i 站。遍历 bookings[]:bookings[i] = [i, j, k] 表示在 i 站增加 k 人即 counters[i] += k
,在 j+1 站减少 k 人即 counters[j + 1] -= k
遍历(整理)counter[] 数组,得到每站总人数: 每站的人数为前一站人数加上当前人数变化 counters[i] += counters[i - 1]
class Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] gap = new int[n + 2];
gap[0] = 0;
for (int[] booking : bookings) {
int from = booking[0];
int end = booking[1];
int count = booking[2];
// 在 from 上车 count 人
gap[from] += count;
// 在 end + 1 下车 count 人
gap[end + 1] -= count;
}
for (int i = 1; i <= n; i ++) {
gap[i] += gap[i - 1];
}
return Arrays.copyOfRange(gap, 1, n + 1);
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10