LeetCode 1109 Corporate Flight Bookings

标签: 数组类题目 LeetCode 发布于:2022-02-12 16:35:42 编辑于:2022-02-12 17:04:00 浏览量:1087

概述

https://leetcode.com/problems/corporate-flight-bookings/

暴力法

时间复杂度 O(n^2),TLE 了。

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> ans(n, 0);
        for (auto& b : bookings) {
            for (int i = b[0] - 1; i <= b[1] - 1; i ++) {
                ans[i] += b[2];
            }
        }
        return ans;
    }
};

差分数组

注意到这里都是按范围预约的航班,我们既然不能暴力遍历,就得想一下如何利用范围构造某种数据结构。

我们的差分数组里存的范围都是从 0 开始的。

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n, 0);
        for (auto& b : bookings) {
            diff[b[1] - 1] += b[2];
            if (b[0] - 2 >= 0) diff[b[0] - 2] -= b[2];
        }
        
        vector<int> ans(n, 0);
        int sum = 0;
        for (int i = n - 1; i >= 0; i --) {
            ans[i] = diff[i] + sum;
            sum += diff[i];
        }
        return ans;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/