查看: 413|回复: 4
收起左侧

[数组] 差分数组是什么意思?

|只看干货
mc2 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (260)
 
 
2% (6)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

总是在有些题解里面看到

一个数组,频繁区间修改操作比如➕和➖,如果频繁修改则复杂度上到O(n2)。
应该怎么做?在区间的开始加一在区间结束的元素处➖一,然后依次迭代。

差分数组
https://leetcode.com/problems/mi ... rray-complementary/
就是一个例子。使用一次变换可以完成一个区间内任意一个数的生成。

请问我理解的对不对。另外英文差分数组是什么?diff array?


评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分


上一篇:哪些证在美国找工作有含金量啊
下一篇:谁能给挨步讲讲这道宇宙难题1483. Kth Ancestor of a Tree Node讨论区中lee215的答案
 楼主| mc2 2021-10-23 08:38:27 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   97% (260)
 
 
2% (6)    👎
差15分才能看面经。还请各位援手,谢谢了
回复

使用道具 举报

yangff 2021-10-23 09:44:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (96)
 
 
5% (6)    👎

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

Alyssa_ 2021-10-23 23:32:53 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (3019)
 
 
4% (152)    👎
开头加一之后计算前缀和数组,区间里的都加上了,结尾减下去,区间外不该加的都减掉了
回复

使用道具 举报

RaccoonPanda 2021-10-25 14:50:45 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (109)
 
 
1% (2)    👎
本帖最后由 RaccoonPanda 于 2021-10-25 15:02 编辑

差分数组不是记录数组本身,而是记录跟前一个数字的差,例如:d[1,3,3,2,4]记录成:f[1,2,0,-1,2],显然d[k]=f[0]+…+f[k]
推论:S[k]=d[0]+…+d=k*d[0]+(k-1)d[1]+…+1*d[k]
注意:我们在计算所有d[k]的时候,可以从左到右依次相加一遍即可:d[k] = d[k-1]+f[k],可以用一个循环解决而不是傻傻地一个一个求。

这个东西在合并区间时候非常有用,比如给你几个区间:[3,5],[2,4],[2,3](m=3个),你要是定义一个[0,5](区间最大为n=5)的array,然后一个一个去添加,那多麻烦呀,时间复杂度是O(mn),但是你分别记成[0,0,0,1,0,0,-1],[0,0,1,0,0,-1],[0,0,1,0,-1],合并起来就可以这么做:
一开始定义一个长度为6(也就是n+1)的数组:
a[0,0,0,0,0,0,0]
读取[3,5]:把a[3]+1,a[6]-1:a[0,0,0,1,0,0,-1]读取[2,4]:把a[2]+1,a[5]-1: a[0,0,1,1,0,-1,-1]
读取[2,3]:把a[2]+1,a[4]-1:a[0,0,2,1,-1,-1,-1]
(读取和操作m次)
然后把a看作差分数组,求原数组,从左到右依次相加即可:
for (int k = 1; k <= 6; k++) a[k] = a[k-1] + a[k]
[0, 0+0=0, 0+2=2, 2+1=3, 3-1=2, 2-1=1, 1-1=0]
(计算n次)
即:[0,0,2,3,2,1,0],也就是,a[2]被覆盖2层,a[3]被覆盖3层,a[4]被覆盖2层,a[5]被覆盖1层。
这样时间复杂度就变成了O(m+n),远小于O(mn)



回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表