admin管理员组

文章数量:1616032

题目地址：

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

给定一个 0 0 0数组 A A A，然后执行若干次操作，每次操作将 A A A的第 i i i到第 j j j个数字都加上某个数字 x x x，问结果数组。

思路是差分数组，可以以 O ( 1 ) O(1) O(1)的时间应答每次询问。代码如下：

public class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n];
        for (int[] booking : bookings) {
            int l = booking[0] - 1, r = booking[1] - 1;
            diff[l] += booking[2];
            if (r + 1 < n) {
                diff[r + 1] -= booking[2];
            }
        }
        
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = i > 0 ? diff[i] + res[i - 1] : diff[i];
        }
        
        return res;
    }
}

时间复杂度 O ( q ) O(q) O(q)（ q q q为操作次数），空间 O ( n ) O(n) O(n)。

本文标签： LeetCodeCorporateBookingsFlight

版权声明：本文标题：【Leetcode】1109. Corporate Flight Bookings 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1728724614a1170593.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。