本文主要是介绍Leetcode1109. 航班预订统计,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Every day a Leetcode
题目来源:1109. 航班预订统计
解法1:差分数组
注意到一个预订记录实际上代表了一个区间的增量。我们的任务是将这些增量叠加得到答案。因此,我们可以使用差分解决本题。
代码:
/** @lc app=leetcode.cn id=1109 lang=cpp** [1109] 航班预订统计*/// @lc code=start// 差分数组class Solution
{
public:vector<int> corpFlightBookings(vector<vector<int>> &bookings, int n){// 构造差分数组vector<int> diff(n + 1, 0);for (vector<int> &booking : bookings){int first = booking[0];int last = booking[1];int seats = booking[2];diff[first - 1] += seats;diff[last] -= seats;}int sum = 0;vector<int> ans;for (int i = 0; i < n; i++){sum += diff[i];ans.push_back(sum);}return ans;}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(n+m),其中 n 是航班数,m 是数组 bookings 的元素个数。
空间复杂度:O(n),其中 n 是航班数。
这篇关于Leetcode1109. 航班预订统计的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!