乐趣区

关于算法:数组三道题学会差分数组

jiezi

前言

上篇文章讲了前缀和前缀和数组，这篇文章开始讲查分数组。另外，数组有下图这些知识点与技巧。

思路

场景：频繁对原始数组的某个区间的元素进⾏增减。原数组 nums 与差分数组 diff 如下图所示。

区间加法

leetcode 第 370 题

解题思路
间接在差分数组上做操作：diff[startIndex] = diff[startIndex] + inc，diff[endIndex + 1] = diff[endIndex + 1] – inc。
这就代表了原数组 nums 的 startIndex 到 endIndex 地位的元素都加上 inc。
但当 endIndex 就是指向 nums 的最初一个元素时，就无需做 diff[endIndex + 1] = diff[endIndex + 1] – inc 操作了。

复杂度剖析
工夫复杂度：O(n + m)，n 是差分数组的长度，m 是操作的次数。对于每一次操作都要解决一次差分数组，并最初对差分数组求前缀和。
空间复杂度：O(1)，留神返回值不计入空间复杂度。

代码 

class Solution {int[] getModifiedArray(int length, int[][] updates) {int[] diff = new int[length];
      for (int[] u : updates) {diff[u[0]] += u[2];
         if (u[1] < length - 1) {diff[u[1] + 1] -= u[2];
         }
      }
      for (int i = 1; i < length; i++) {diff[i] = diff[i - 1] + diff[i];
      }
      return diff;
   }
}

航班预订统计

leetcode 第 1109 题

解题思路
思路与《区间加法》基本一致。但要留神操作数组中的下标是从 1 开始而不是 0。

复杂度剖析
工夫复杂度：O(n + m)，n 是差分数组的长度，m 是操作的次数。对于每一条预约记录都要解决一次差分数组，并最初对差分数组求前缀和。
空间复杂度：O(1)，留神返回值不计入空间复杂度。

代码 

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

拼车

leetcode 第 1094 题

解题思路
留神 toi 下标对应的含意为乘客在此处下车，那么差分数组须要在此处减去对应的乘客数。
在最初将差分数组转化为原数组进行判断是否超载时，必须要额定判断原数组第 0 项是否超载（这里很容易脱漏）。

复杂度剖析

工夫复杂度：O(n + m)，n 是差分数组的长度，m 是操作的次数。对于每一次旅行都要解决一次差分数组，并最初对差分数组求前缀和。
空间复杂度：O(n)，须要额定空间存储查分数组。

代码 

class Solution {public boolean carPooling(int[][] trips, int capacity) {
       // 先找出所有乘客下车的站中的最大的那个站
      int max = Stream.of(trips).max(Comparator.comparingInt(o -> o[2])).map(o -> o[2]).get();
      int len = max + 1;
      int[] diff = new int[len];
      for (int[] u : trips) {diff[u[1]] += u[0];
         // 留神，在哪个站站下车，差分数组就须要在对应的下表处做减法
         if (u[2] < len) {diff[u[2]] -= u[0];
         }
      }
      // 差分数组 / 元素组的第 0 项也要做判断
      if (diff[0] > capacity) {return false;}
      for (int i = 1; i < len; i++) {diff[i] = diff[i - 1] + diff[i];
         if (diff[i] > capacity) {return false;}
      }
      return true;
    }
}

结尾

通过三道差分数组算法题的练习，置信你学会了其中的精华了。下一篇算法文章讲双指针之快慢指针。

微信扫描下方二维码，关注公众号后回复【笔记】，有我筹备的 15 万字 Java 面试笔记。

感激各位人才的点赞、珍藏和评论，干货文章继续更新中，下篇文章再见！

退出移动版