标签搜索

目 录CONTENT

文章目录

差分数组.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 8 阅读 / 3,455 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

差分数组

@

一、前缀和

前缀和主要适用的场景是原始数组不会被修改的情况下,频繁查询某个区间的累加和

  • 核心代码就是下面这段:
class PrefixSum 
{
    // 前缀和数组
    private int[] prefix;

    /* 输入一个数组,构造前缀和 */
    public PrefixSum(int[] nums) 
    {
        prefix = new int[nums.length + 1];
        // 计算 nums 的累加和
        for (int i = 1; i < prefix.length; i++) 
        {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
    }

    /* 查询闭区间 [i, j] 的累加和 */
    public int query(int i, int j) 
    {
        return prefix[j + 1] - prefix[i];
    }
}

在这里插入图片描述

  • prefix[i]就代表着nums[0..i-1]所有元素的累加和,如果我们想求区间nums[i..j]的累加和,只要计算prefix[j+1] - prefix[i]即可,而不需要遍历整个区间求和

二、差分数组

本文讲一个和前缀和思想非常类似的算法技巧「差分数组」,差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减

  • 比如说,我给你输入一个数组nums,然后又要求给区间nums[2…6]全部加 1,再给nums[3…9]全部减 3,再给nums[0…4]全部加 2,再给…

  • 一通操作猛如虎,然后问你,最后nums数组的值是什么?

  • 常规的思路很容易,你让我给区间nums[i..j]加上val,那我就一个 for 循环给它们都加上呗,还能咋样?这种思路的时间复杂度是 O(N),由于这个场景下对nums的修改非常频繁,所以效率会很低下

  • 这里就需要差分数组的技巧,类似前缀和技巧构造的prefix数组,我们先对nums数组构造一个diff差分数组,diff[i]就是nums[i]和nums[i-1]之差

int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) 
{
    diff[i] = nums[i] - nums[i - 1];
}

在这里插入图片描述

  • 通过这个diff差分数组是可以反推出原始数组nums的,代码逻辑如下:
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) 
{
    res[i] = res[i - 1] + diff[i];
}
  • 这样构造差分数组diff,就可以快速进行区间增减的操作,如果你想对区间nums[i..j]的元素全部加 3,那么只需要让diff[i] += 3,然后再让diff[j+1] -= 3即可
    在这里插入图片描述

  • 原理很简单,回想diff数组反推nums数组的过程,diff[i] += 3意味着给nums[i..]所有的元素都加了 3,然后diff[j+1] -= 3又意味着对于nums[j+1..]所有元素再减 3,那综合起来,是不是就是对nums[i..j]中的所有元素都加 3 了

  • 只要花费 O(1) 的时间修改diff数组,就相当于给nums的整个区间做了修改。多次修改diff,然后通过diff数组反推,即可得到nums修改后的结果

现在我们把差分数组抽象成一个类,包含increment方法和result方法:

class Difference 
{
    // 差分数组
    private int[] diff;

    public Difference(int[] nums) 
    {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) 
        {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i,j] 增加 val(可以是负数)*/
    public void increment(int i, int j, int val) 
    {
        diff[i] += val;
        if (j + 1 < diff.length) 
        {
            diff[j + 1] -= val;
        }
    }

    public int[] result() 
    {
        int[] res = new int[diff.length];
        // 根据差分数组构造结果数组
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) 
        {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

这里注意一下increment方法中的 if 语句:

public void increment(int i, int j, int val) 
{
    diff[i] += val;
    if (j + 1 < diff.length) 
    {
        diff[j + 1] -= val;
    }
}
  • 当j+1 >= diff.length时,说明是对nums[i]及以后的整个数组都进行修改,那么就不需要再给diff数组减val了。

三、问题描述

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

在这里插入图片描述
在这里插入图片描述

四、分析

这个题目就在那绕弯弯,其实它就是个差分数组的题,我给你翻译一下:

  • 给你输入一个长度为n的数组nums,其中所有元素都是 0。
  • 再给你输入一个bookings,里面是若干三元组(i,j,k),每个三元组的含义就是要求你给nums数组的闭区间[i-1,j-1]中所有元素都加上k。
  • 请你返回最后的nums数组是多少?

PS:因为题目说的n是从 1 开始计数的,而数组索引从 0 开始,所以对于输入的三元组(i,j,k),数组区间应该对应[i-1,j-1]。

这么一看,不就是一道标准的差分数组题嘛?我们可以直接复用刚才写的类:

int[] corpFlightBookings(int[][] bookings, int n) 
{
    // nums 初始化为全 0
    int[] nums = new int[n];
    // 构造差分解法
    Difference df = new Difference(nums);

    for (int[] booking : bookings) 
    {
        // 注意转成数组索引要减一哦
        int i = booking[0] - 1;
        int j = booking[1] - 1;
        int val = booking[2];
        // 对区间 nums[i..j] 增加 val
        df.increment(i, j, val);
    }
    // 返回最终的结果数组
    return df.result();
}

五、完整代码

// 构造差分数组
class Difference 
{
    public:
    Difference(vector<int> nums) 
    {
        assert(nums.size() > 0);
        diff.resize(nums.size(),0);

        // 构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) 
        {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i,j] 增加 val(可以是负数)*/
    void increment(int i, int j, int val) 
    {
        diff[i] += val;
        if (j + 1 < diff.size()) 
        {
            diff[j + 1] -= val;
        }
    }

	// 返回构造的结果
    vector<int> result() 
    {
        vector<int> ret(diff.size());
        
        // 根据差分数组构造结果数组
        ret[0] = diff[0];
        for (int i = 1; i < diff.size(); i++) 
        {
            ret[i] = ret[i - 1] + diff[i];
        }
        return ret;
    }

    private:
    vector<int> diff;
};

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    	// 原始数组
        vector<int> nums(n,0);
        
        Difference df(nums);
		
		// 循环遍历给nums数组区间进行+
        for(auto& e : bookings)
        {
            int i = e[0] - 1;
            int j = e[1] - 1;
            int val = e[2];
            df.increment(i,j,val);
        }

        return df.result();
    }
};

0

评论区