快捷搜索:  汽车  科技

数组整体可以参加各种数学运算吗(数组-三道题学会差分数组)

数组整体可以参加各种数学运算吗(数组-三道题学会差分数组)解题思路  思路与《区间加法》基本一致。但要注意操作数组中的下标是从1开始而不是0。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]; }

前言

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

数组整体可以参加各种数学运算吗(数组-三道题学会差分数组)(1)

思路

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

数组整体可以参加各种数学运算吗(数组-三道题学会差分数组)(2)

区间加法

leetcode第370题

数组整体可以参加各种数学运算吗(数组-三道题学会差分数组)(3)

解题思路
  直接在差分数组上做操作: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题

数组整体可以参加各种数学运算吗(数组-三道题学会差分数组)(4)

数组整体可以参加各种数学运算吗(数组-三道题学会差分数组)(5)

解题思路
  思路与《区间加法》基本一致。但要注意操作数组中的下标是从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题

数组整体可以参加各种数学运算吗(数组-三道题学会差分数组)(6)

解题思路
  注意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面试笔记。

数组整体可以参加各种数学运算吗(数组-三道题学会差分数组)(7)

  感谢各位人才的点赞、收藏和评论,干货文章持续更新中,下篇文章再见!

猜您喜欢: