网站建设公司哪个好呀,网站策划软件,商丘建设网站,wordpress 主题后台Every day a Leetcode
题目来源#xff1a;1109. 航班预订统计
解法1#xff1a;差分数组
注意到一个预订记录实际上代表了一个区间的增量。我们的任务是将这些增量叠加得到答案。因此#xff0c;我们可以使用差分解决本题。 代码#xff1a;
/** lc appleetcode.cn i…Every day a Leetcode
题目来源1109. 航班预订统计
解法1差分数组
注意到一个预订记录实际上代表了一个区间的增量。我们的任务是将这些增量叠加得到答案。因此我们可以使用差分解决本题。 代码
/** lc appleetcode.cn id1109 langcpp** [1109] 航班预订统计*/// lc codestart// 差分数组class Solution
{
public:vectorint corpFlightBookings(vectorvectorint bookings, int n){// 构造差分数组vectorint diff(n 1, 0);for (vectorint booking : bookings){int first booking[0];int last booking[1];int seats booking[2];diff[first - 1] seats;diff[last] - seats;}int sum 0;vectorint ans;for (int i 0; i n; i){sum diff[i];ans.push_back(sum);}return ans;}
};
// lc codeend结果 复杂度分析
时间复杂度O(nm)其中 n 是航班数m 是数组 bookings 的元素个数。
空间复杂度O(n)其中 n 是航班数。
