航班预订统计分析

熊孩纸 阅读:423 2020-10-22 16:42:41 评论:0

这里有 n 个航班,它们分别从 1 到 n 进行编号。

我们这儿有一份航班预订表,表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。

请你返回一个长度为 n 的数组 answer,按航班编号顺序返回每个航班上预订的座位数。

解:这道题用暴力的方法很简单,用一个set按航班号为key存储就好了

下面这种方法,只用了O(N)的复杂度就解决了

首先我们将对一个区间的操作转化为左、右两个端点上的操作

如对于 bookings = [1, 3, 10] n = 5

我们正常解法为在 1-3 位置上各加1如图所示

 

 

 

转换为使用端点表示为:从1开始+10, 从4开始不加,那我们就标记位置1为10,位置4 为 -10如图:

 

 

 

在统计时 记res[i] = res[i] + res[i - 1] (i > 0)

 

 

 

那么对于 多个区间,我们只需要叠加起来即可

 

 

class Solution { 
public: 
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) { 
        int length =bookings.size(); 
        //tag记录第i个相比i-1的变量 
        vector<int> tag(n,0); 
        int l=0,r=0,seat=0; 
        for(int index=0;index<length;index++) 
        { 
            //作为下标,减掉1从0开始 
            l=bookings[index][0]-1; 
            r=bookings[index][1]-1; 
            seat=bookings[index][2]; 
            tag[l]+=seat; 
            if(r+1<n) 
            { 
                tag[r+1]-=seat; 
            } 
        } 
 
        //这里之后tag表示的就不是差值而是每次相加后的实际值 
        //第一个值不算差值么,这个是我写代码时疑惑的地方,想明白后其实第一个值就是差值自身 
        for(int index=1;index<n;index++) 
        { 
            tag[index]+=tag[index-1]; 
        } 
        return tag; 
    } 
};

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号