航班预订统计(差分算法)

x33g5p2x  于10个月前 转载在 其他  
字(0.4k)|赞(0)|评价(0)|浏览(96)

在这里插入图片描述

在这里插入图片描述

数据量大,用暴力方法解决必定超时。

//差分算法
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {

        vector<int>ans(n); //差分数组,每个元素存储ans[i]-ans[i]的值

        for(auto booking:bookings){
            ans[booking[0]-1]+=booking[2];
            if(booking[1]<n){
                 ans[booking[1]]-=booking[2];
            }
        }
        
        //求出差分数组的前缀和数组即得到原数组
        for(int i=1;i<n;i++)
            ans[i]=ans[i-1]+ans[i];

        return ans;
    }
};

相关文章