差分数组的性质

差分数组的性质

  1. 定义 : 对于已知有n个元素的离线数列d,我们可以建立记录它每项与前一项差值的差分数组f:显然,f[1]=d[1]-0=d[1];对于整数i∈[2,n],我们让f[i]=d[i]-d[i-1]。
  2. 性质 : 原数组可以用差分数组的前缀和求得。
  3. 用途: 3.1 快速处理区间[left, right]上的数加x,通过性质可知道,第一个受影响的差分数组元素为f[left], 即令f[left]+=x, 那么之后的元素在计算过程中都会加上x。 最后一个受影响的查分数组元素为f[right],所以在f[right+1]处需要矫正,即f[right+1]-=x,即可保证right+1之后的元素不被影响。这样的话不必对[left,right]范围之内所有数进行处理。
  4. leetcode例题: 1109. 航班预订统计
题目
  这里有 n :个航班,它们分别从 1 到 n 进行编号。

  有一份航班预订表 bookings ,表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti (包含 firsti 和 lasti )的 每个航班 上预订了 seatsi 个座位。

  请你返回一个长度为 n 的数组 answer,其中 answer[i] 是航班 i 上预订的座位总数。
python:
class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        ans = [0]*n
        for l, r, s in bookings:
            ans[l-1] += s
            if r < n:
                ans[r] -= s
        for i in range(1, n):
            ans[i] += ans[i-1]
        return ans
        
        
C++:
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> ans (n);
        for (auto& book : bookings){
            ans[book[0]-1] += book[2];
            if (book[1] < n){
                ans[book[1]] -= book[2];
            }
        }
        for (int i = 1; i < n; i++){
            ans[i] += ans[i-1];
        }
        return ans;
    }
};


多谢支持~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦