Running Noob

Do Something Meaningful

0%

差分数组

发表于 分类于
本文字数： 971 阅读时长 ≈ 4 分钟
  • 差分数组是一种用于高效处理数据序列上一段区间内每个元素增减同一个值的技术。它常用于数组和列表数据结构中，可以让区间修改的操作时间复杂度降低到O(1)，查询操作的时间复杂度为O(n)。

差分数组

  • 差分数组是一种用于高效处理数据序列上一段区间内每个元素增减同一个值的技术。它常用于数组和列表数据结构中，可以让区间修改的操作时间复杂度降低到O(1)，查询操作的时间复杂度为O(n)。 差分数组技巧适用场合：频繁对数组的某个区间的元素进行增减。

  • 假设有一个初始数组 arr，长度为 n。**差分数组 diff 定义为每个位置上的元素与前一个元素的差值，即 diff[i] = arr[i] - arr[i-1]**，在给区间增加或减小某个数时，我们始终只维护差分数组。为了方便处理，我们通常令 diff[0] = arr[0]。

    再直观地说，diff[i] 就表示 arr[i] 比 arr[i-1] 大多少（可以是负数），所以根据 arr[i-1] + diff[i] 就可以得到arr[i]。我们总是维护一个和数组 arr 相关的 diff，并且 diff[0] 一直与 arr[0] 相等，因此任意时刻可以复原 arr 数组。

    • 给定数组 arr，构建差分数组 diff 的过程如下：
      1. 初始化 diff[0] = arr[0]。
      2. 对于 arr 中的每个元素 arr[i]（ i 从 1 开始），令 diff[i] = arr[i] - arr[i-1]。

  • 那么差分数组有什么用呢？有以下两种常见的场景：

    1. 区间修改：如果要将 arr 中从 l 到 r（包括两端点）的所有元素都加上一个值 v，我们只需要对差分数组做两步操作：

      • **diff[l] += v**，这意味着 arr 中的元素从位置 l 开始，每个元素都增加了 v。（注意这里只是对 diff[l] 加了一个 v）
      • **如果 r + 1 < n，则 diff[r + 1] -= v**，这意味着从位置 r + 1 开始，arr 的每个元素应该恢复原来的值，不再增加v。

      举个例子，对数组 arr = {1, 2, 3, 4}，其差分数组为 diff = {1, 1, 1, 1}。如果要对 [1,2] 区间内的数字加 10，则将 diff 数组的值更新为 diff = {1, 11, 1, -9} 即可。可以看到，只对 diff[1] 和 diff[3] 的数据进行了修改。

      • 通过上述操作，我们在 O(1) 时间内完成了区间修改。

    2. 查询操作：要恢复 arr 中的某个元素值，或者得到修改后的数组，我们只需要对差分数组 diff 做前缀和操作。具体来说，arr[i] = diff[0] + diff[1] + ... + diff[i]。值得注意的是：diff[0] 永远保持着真实的 arr[0] 的值。

    差分数组最大的优势在于能够非常高效地对原始数组的连续区间进行增减操作。在处理大量区间增减值的问题时，差分数组能够大幅度减少计算量，尤其是在数据量大、修改操作频繁的情况下。

1.航班预订统计

题目

  • 这里有 n 个航班，它们分别从 1 到 n 进行编号。

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

    请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

    示例 1：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
    输出：[10,55,45,25,25]
    解释：
    航班编号        1   2   3   4   5
    预订记录 1 ：   10  10
    预订记录 2 ：       20  20
    预订记录 3 ：       25  25  25  25
    总座位数：      10  55  45  25  25
    因此，answer = [10,55,45,25,25]

    示例 2：

    1
    2
    3
    4
    5
    6
    7
    8
    输入：bookings = [[1,2,10],[2,2,15]], n = 2
    输出：[10,25]
    解释：
    航班编号        1   2
    预订记录 1 ：   10  10
    预订记录 2 ：       15
    总座位数：      10  25
    因此，answer = [10,25]

    提示：

    • 1 <= n <= 2 * 104
    • 1 <= bookings.length <= 2 * 104
    • bookings[i].length == 3
    • 1 <= firsti <= lasti <= n
    • 1 <= seatsi <= 104

思路

  • 因为是频繁对区间的修改，所以可以考虑使用差分数组。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
        public int[] corpFlightBookings(int[][] bookings, int n) {
            int[] answer = new int[n];
            int[] diff = new int[n];
            // 差分数组第一项：diff[0] = arr[0]
            diff[0] = 0;
            for (int i = 0; i < bookings.length; i++) {
                // 因为航班从1开始编号，所以要-1
                int first = bookings[i][0] - 1;
                int last = bookings[i][1] - 1;
                int seats = bookings[i][2];
                // 使用差分数组的思想
                diff[first] += seats;
                if (last + 1 < n) {
                    diff[last + 1] -= seats;
                }
            }
            // 最后由差分数组得到结果
            answer[0] = diff[0];
            for (int i = 1; i < n; i++) {
                answer[i] = answer[i - 1] + diff[i];
            }
            return answer;
        }
    }
---------------The End---------------