大家好,欢迎来到IT知识分享网。
前缀和主要适用的场景是原始数组不会被修改的情况下,频繁查询某个区间的累加和。
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。
class Difference:
def __init__(self, nums):
self.nums = nums
self.diff = self.make_diff(self.nums)
def make_diff(self, nums):
diff = [0 for _ in range(len(nums))]
diff[0] = nums[0]
for i in range(1,len(nums)):
diff[i] = nums[i] – nums[i-1]
return diff
# 给闭区间[i,j]增加val
# 原理很简单,回想diff数组反推nums数组的过程,diff[i] += 3意味着给nums[i..]所有的元素都加了 3,然后diff[j+1] -= 3又意味着对于nums[j+1..]所有元素再减 3,那综合起来,是不是就是对nums[i..j]中的所有元素都加 3 了?
def increment(self, i, j, val):
self.diff[i] += val
if j + 1 < len(self.diff):
self.diff[j + 1] -= val
def recover(self):
rdiff = [0 for _ in range(len(self.diff))]
rdiff[0] = self.diff[0]
for i in range(1,len(self.nums)):
rdiff[i] = rdiff[i-1] + self.diff[i]
return rdiff
difference = Difference([8,5,9,6,1])
print(difference.diff)
rdiff = difference.recover()
print(rdiff)
difference.increment(2,3,1)
print(difference.diff)
rdiff = difference.recover()
print(rdiff)
结果:
[8, -3, 4, -3, -5]
[8, 5, 9, 6, 1]
[8, -3, 5, -3, -6]
[8, 5, 10, 7, 1]
不妨去试试力扣第 1109 题「航班预订统计]。
labuladong的算法小抄
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/15940.html