差分数组 & 技巧小记

这篇具有很好参考价值的文章主要介绍了差分数组 & 技巧小记。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 


差分数组

如果两个信息“长得很像”,只要保留一个,对另一个,只要保留它们的差异,然后进行微调就行了。

差分数组:

  • 3210,3208,3206,3211,3220,3212……
  • 3210 【-2】【-2】【5】【9】【-8】……

适用场景,频繁对某个区间的元素进行增减。

// 初始化差分数组
diff[0] = nums[0];                         // 以第一个值为基础
for (int i = 1; i < nums.length; i++) 
    diff[i] = nums[i] - nums[i - 1];       // 存储差分值

对区间 nums[i…j] 的元素全部加 5:

  • diff[i] += 5
  • diff[j+1] -= 5(记得j+1是不需要的)

对区间 nums[i…j] 的元素全部减 5:

  • diff[i] += -5(减 5 以加 -5 的方式)
  • diff[j+1] -= -5(记得j+1是不需要的)
// 修改差分数组
void add(int l, int r, int c) {
    diff[l] += c;
    if( r+1 < diff.length )   
    	diff[r+1] -= c;
}

对比常规,给一个区间 [l,r] 上的数组加一个常数c, [l,r] 每个元素都要依次加上c,这样的时间复杂度是 O(n) 的。

而差分数组只修改头、尾,O(1) 的时间。
 


二维差分

差分数组 & 技巧小记
这个人写得好:https://blog.csdn.net/m0_74215326/article/details/129620912文章来源地址https://www.toymoban.com/news/detail-431871.html

到了这里,关于差分数组 & 技巧小记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法专题:差分数组

    2024年01月18日
    浏览(32)
  • 差分数组详解

    一维差分数组 假设给你一个数组 nums ,先对区间 [a,b] 中每个元素加 3 ,在对区间 [c,d] 每个元素减 5 …… ,这样非常频繁的区间修改,常规的做法可以一个个计算。 频繁对数组的一段区间进行增加或减去同一个值,如果一个个去操作,很明显效率很差,我们可以使用差分数

    2024年02月08日
    浏览(49)
  • 【算法】【差分数组】解决连续空间改变相同值的问题

    将原数组每个值减去前一个值,得到的新数组是差分数组 d i s [ k ] = a [ k ] − a [ k − 1 ] dis[k] = a[k] - a[k-1] d i s [ k ] = a [ k ] − a [ k − 1 ] 如: 原数组为 [ 1 , 2 , 3 , 5 ] [1,2,3,5] [ 1 , 2 , 3 , 5 ] 得到的差分数组为 [ 1 , 1 , 1 , 2 ] [1,1,1,2] [ 1 , 1 , 1 , 2 ] 通过计算差分数组的前缀和,可以得

    2024年02月08日
    浏览(74)
  • 检查Javascript对象数组中是否存在对象值,如果没有向数组添加新对象

    需求: 如果我有以下对象数组: 有没有办法循环遍历数组,以检查特定的用户名值是否已经存在,如果它什么都不做,但是如果它没有用所述用户名(和新的ID)将新对象添加到数组? 解决 方法 一: 我假设id s在这里是独一无二的。 some是检查数组中事物存在的一个很好的函数

    2024年02月11日
    浏览(42)
  • 【面试题】:axios二次封装都进行了哪些配置以及如果项目里面有两个baseURL你怎么解决?

    一.axios的概念         Axios 是一个基于  promise  网络请求库,作用于node.js 和浏览器中。 它是  isomorphic  的(即同一套代码可以运行在浏览器和node.js中)。在服务端它使用原生 node.js  http  模块, 而在客户端 (浏览端) 则使用 XMLHttpRequests。 二.axios的特点(不常问) 从浏览

    2024年02月11日
    浏览(41)
  • 【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目

    【动态规划】【数学】【C++算法】18赛车 差分数组 图论 分类讨论 整除以2 给你三个 正整数 n 、x 和 y 。 在城市中,存在编号从 1 到 n 的房屋,由 n 条街道相连。对所有 1 = i n ,都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与

    2024年01月22日
    浏览(35)
  • js两个数组对象去重,删除两个数组中相同的对象、删除数组对象中某个对象

    模拟一些数据: 方式一:两个数组通过arr1的id和arr2的id比较,返回去重后的arr1  写法二 打印的结果:console.log(newArr); 方式二:删除两个数组对象中相同的对象 方式三:es6 去掉两个数组中相同值的对象 删除数组中某一个对象、指定的对象 数组删除其中的对象或元素,在前端

    2023年04月09日
    浏览(43)
  • 力扣_数组26—合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,

    2024年01月21日
    浏览(43)
  • 【面试经典150 | 数组】合并两个有序数组

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年02月09日
    浏览(45)
  • 从优秀源码中学到的两个技巧

      在实际开发中为了避免命名空间污染,一般都不会using namespace std。但是如果一个对象写起来比较复杂,用using能大幅度地简化操作。现在假设我们要设计一个函数,它在一个作用域里面,使用它只能以A::B::C()这种形式。思考一下,如果我们放在命名空间下,是可以被usi

    2024年02月08日
    浏览(28)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包