北京网站seo优化推广,网络广告营销策划方案,idstore wordpress,动态设计用什么软件差分数组
差分数组是什么#xff1f;
**举例#xff1a;**对于数组考虑数组 a[1,3,3,5,8]#xff0c;对其中的相邻元素两两作差#xff08;右边减左边#xff09;#xff0c;得到数组 [2,0,2,3]。然后在开头补上 a[0]#xff0c;得到差分数组#xff1a;
d[1,2,0…差分数组
差分数组是什么
**举例**对于数组考虑数组 a[1,3,3,5,8]对其中的相邻元素两两作差右边减左边得到数组 [2,0,2,3]。然后在开头补上 a[0]得到差分数组
d[1,2,0,2,3]
如果对数组进行从左往右累加d中的元素就对差分数组进行了还原即还原成了数组a
a[1,3,3,5,8]
所以差分数组定义为差分数组是一个数组其中每个元素表示原始数组中相邻元素之间的差值。这种数组通常用于解决区间增量更新和查询的问题。
差分数组与前缀和相对应。差分数组通过前缀和求取原始数组前缀和可以通过差分数组返回原始数组
差分数组怎么计算
如果有一个原始数组 nums差分数组 diff 的计算方式如下
第一个元素 diff[0] 等于原始数组的第一个元素 nums[0]。对于 i 0 的每个位置diff[i] nums[i] - nums[i - 1]。
举例nums [1, 3, 2, 4, 1]的差分数组为diff [1, 2, -1, 2, -3]
差分数组有什么用
通过差分数组可以在 O(1) 时间内对原始数组的某个区间进行增量更新而无需修改整个区间的值。对差分数组进行更新时可以通过修改两个位置的值来实现
对于区间 [left, right] 的增量 valdiff[left] 增加 valdiff[right 1] 减去 val。举例 数组nums [1, 3, 2, 4, 1]的差分数组为diff [1, 2, -1, 2, -3]对数组nums[1],nums[2],nums[3]都加上10得到nums [1, 13, 12, 14, 1]对数组进行作差并在开头补上nums[0]nums[0],得到差分数组diff [1, 12, -1, 2, -13]对比两个差分数组diff [1, 2, -1, 2, -3]diff [1, 12, -1, 2, -13]可以发现只有diff[1]和diff[4]发生了变化这意味着对 nums数组的操作可以转变成对差分数组 diff的两个数操作。
这种方式在处理大规模数组的增量操作时非常高效因为它只需要修改差分数组的少数几个元素然后再根据差分数组重新构建原始数组。
差分数组的性质
性质 1从左到右累加 diff*中的元素可以得到数组 nums
性质2 以下两种操作是等价的
把 nums的子数组nums[i], nums[i1], …, nums[j]都加上x。- 把 diff[i] 增加 x把 d[j1] 减少 x。
性质3 如果nums数组全为0那么差分数组diff也全为0
利用性质 2我们只需要 O(1) 的时间就可以完成对 nums 的子数组的操作。最后利用性质 1 从差分数组复原出数组 nums。
Leetcode题目
1094. 拼车
题目
题目链接1094. 拼车
题目描述车上最初有 capacity 个空座位。车 只能 向一个方向行驶也就是说不允许掉头或改变方向
给定整数 capacity 和一个数组 trips , trip[i] [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时返回 true否则请返回 false。
示例 1
输入trips [[2,1,5],[3,3,7]], capacity 4
输出false示例 2
输入trips [[2,1,5],[3,3,7]], capacity 5
输出true思路 初始化一个数组 diff表示差分数组用于记录各个站点的乘客数量站点编号从 1 开始。 对于每个 trip其中 trip[i](c, a, b) 表示有 c 个乘客在 a 站上车在 b 站下车。对差分数组 nums 区间**[a,b)****注意是左开右闭因为在b站点就下车了。**进行操作 diff[a] cdiff[b] - c 处理完所有 trips 后对差分数组 diff 进行前缀计算即累加数组中的值得到各个站点的乘客数量。 最后将各个站点的乘客数量与给定的 capacity 比较判断是否超载。 注意 人为规定站点编号从 1 开始。
代码
class Solution {public boolean carPooling(int[][] trips, int capacity) {//差分数组对某段区间可以实现快速的进行同一个操作再利用前缀和进行恢复数组int ans[] new int[1010];//计算差分数组for(int i 0; i trips.length; i){int num trips[i][0];int from trips[i][1];int to trips[i][2];ans[from1] num;ans[to1] - num;}//通过前缀和计算每个时间段的乘客人数for(int i 1; i 1000; i){ans[i] ans[i-1];if(ans[i] capacity) return false;}return true;}
}差分数组相关题目 航班预订统计
将区间分为最少组数
字母移位 II
使数组中的所有元素都等于零
最大化城市的最小供电站数目
