网站建设团队扬州,wordpress 添加地图,网站数字化建设方案,不配置iis做网站目录 1.题目2.思路3.代码实现#xff08;Java#xff09; 1.题目
给你一个数组 nums #xff0c;请你完成两类查询。
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间#xff08; 包含 #xff09;的nums元素的… 目录 1.题目2.思路3.代码实现Java 1.题目
给你一个数组 nums 请你完成两类查询。
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间 包含 的nums元素的 和 其中 left right
实现 NumArray 类
NumArray(int[] nums) 用整数数组 nums 初始化对象void update(int index, int val) 将 nums[index] 的值 更新 为 valint sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间 包含 的nums元素的 和 即nums[left] nums[left 1], …, nums[right]
示例 1 输入 [“NumArray”, “sumRange”, “update”, “sumRange”] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] 输出 [null, 9, null, 8] 解释
NumArray numArray new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 3 5 9
numArray.update(1, 2); // nums [1,2,5]
numArray.sumRange(0, 2); // 返回 1 2 5 8提示 1 nums.length 3 * 104 -100 nums[i] 100 0 index nums.length -100 val 100 0 left right nums.length 调用 update 和 sumRange 方法次数不大于 3 * 104
2.思路
1前缀和 使用前缀和的思想来维护原始数组的区间和。
在构造函数中首先初始化原始数组 nums然后计算前缀和 preSum用于记录 0 至 i (包括i) 的和。这里 preSum 的长度比 nums 的长度大 1是因为第一个前缀和 preSum[0] 被初始化为 0用于方便后续的计算。更新操作需要更新原始值和前缀和数组即当 nums[index] 更新为 val 时从 index 1 开始对于 preSum 数组中的每一项更新为原先的值加上该位置对应原始值变化后的差值。查询操作使用前缀和的思想其中 preSum[right 1] 表示 0 至 right 的和preSum[left] 表示 0 至 left - 1 的和两者相减即得[left, right] 的和。 这种方法的时间复杂度为构造对象时为 O(n)更新操作为 O(n)查询操作为 O(1)空间复杂度为 O(n)。 2分块处理 思路参考本题官方题解。
具体实现是在构造方法中首先将原始数组分成若干个大小为 n \sqrt{n} n 的块 n n n 为原始数组的长度并对每个块计算出其元素和保存在 sum 数组中。这样可以通过查询两个块之间元素和的和来计算区间和。对于区间查询可以分为三种情况
区间 [left, right] 在同一个块中直接顺序遍历该块内的元素求和并返回。区间 [left, right] 跨越若干个块分别计算每个块首尾元素与这两个元素之间的元素和再将结果相加得到区间和。特别的对第一个块位于区间左边的部分只计算其位于区间内的部分对最后一个块位于区间右边的部分只计算其位于区间内的部分。如果区间 [left, right] 在一个块的左边、右边、甚至它本不在任何一个块中那就和情况2一样分别计算。
对于单点修改按照数组的更新方式更新每个块的元素和即可。
3线段树 思路参考本题官方题解。
3.代码实现Java
//思路1————前缀和
class NumArray {private int[] nums;private int[] preSum;public NumArray(int[] nums) {int n nums.length;this.nums Arrays.copyOf(nums, n);preSum new int[n 1];for (int i 1; i n 1; i) {preSum[i] preSum[i - 1] nums[i - 1];}}public void update(int index, int val) {int original nums[index];nums[index] val;for (int i index 1; i preSum.length; i) {preSum[i] val - original;}}public int sumRange(int left, int right) {return preSum[right 1] - preSum[left];}
}/*** Your NumArray object will be instantiated and called as such:* NumArray obj new NumArray(nums);* obj.update(index,val);* int param_2 obj.sumRange(left,right);*///思路2————线段树
class NumArray {// sum[i] 表示第 i 个块的元素和private int[] sum; //块的大小private int size;private int[] nums;public NumArray(int[] nums) {this.nums nums;int n nums.length;size (int) Math.sqrt(n);// n / size 向上取整sum new int[(n size - 1) / size]; for (int i 0; i n; i) {sum[i / size] nums[i];}}public void update(int index, int val) {sum[index / size] val - nums[index];nums[index] val;}public int sumRange(int left, int right) {// left 位于第 b1 个块内int b1 left / size;// left 在第 b1 个块内的偏移量int i1 left % size;// right 位于第 b2 个块内int b2 right / size;// right 在第 b2 个块内的偏移量int i2 right % size;//区间 [left, right] 在同一块中if (b1 b2) { int sum 0;for (int j i1; j i2; j) {sum nums[b1 * size j];}return sum;}//计算第 b1 个块位于区间 [i1, size - 1) 的元素和 sum1int sum1 0;for (int j i1; j size; j) {sum1 nums[b1 * size j];}//计算第 b2 个块位于区间 [0, i2] 的元素和 sum2int sum2 0;for (int j 0; j i2; j) {sum2 nums[b2 * size j];}//计算第 b1 1 个块到第 b2 − 1 个块的元素和的总和 sum3int sum3 0;for (int j b1 1; j b2; j) {sum3 sum[j];}return sum1 sum2 sum3;}
}/*** Your NumArray object will be instantiated and called as such:* NumArray obj new NumArray(nums);* obj.update(index,val);* int param_2 obj.sumRange(left,right);*///思路3————线段树
class NumArray {//用于存储区间和的线段树private int[] segmentTree; //原始数组的长度private int n; public NumArray(int[] nums) {n nums.length;//线段树的大小是原始数组长度的 4 倍(稍微比需要的最小长度大一些)segmentTree new int[nums.length * 4]; //构建线段树build(0, 0, n - 1, nums); }public void update(int index, int val) {//更新指定索引处的元素值change(index, val, 0, 0, n - 1); }public int sumRange(int left, int right) {//求解指定区间的和return range(left, right, 0, 0, n - 1);}//构建线段树的递归函数private void build(int node, int s, int e, int[] nums) {if (s e) {//叶节点保存原始数组的元素值segmentTree[node] nums[s]; return;}int m s (e - s) / 2;//递归构建左子树build(node * 2 1, s, m, nums); //递归构建右子树build(node * 2 2, m 1, e, nums); //更新父节点的值为左子树和右子树的和segmentTree[node] segmentTree[node * 2 1] segmentTree[node * 2 2]; }//更新线段树的递归函数private void change(int index, int val, int node, int s, int e) {if (s e) {//叶节点更新原始数组的元素值segmentTree[node] val; return;}int m s (e - s) / 2;if (index m) {//目标索引在左子树中递归更新左子树change(index, val, node * 2 1, s, m);} else {//目标索引在右子树中递归更新右子树change(index, val, node * 2 2, m 1, e); }segmentTree[node] segmentTree[node * 2 1] segmentTree[node * 2 2]; // 更新父节点的值为左子树和右子树的和}//查询线段树中指定区间范围的和的递归函数private int range(int left, int right, int node, int s, int e) {if (left s right e) {//找到了目标区间返回当前节点的值return segmentTree[node]; }int m s (e - s) / 2;if (right m) {//目标区间完全在左子树中递归查询左子树return range(left, right, node * 2 1, s, m); } else if (left m) {//目标区间完全在右子树中递归查询右子树return range(left, right, node * 2 2, m 1, e); } else {//目标区间跨越左右子树分别递归查询左右子树并求和return range(left, m, node * 2 1, s, m) range(m 1, right, node * 2 2, m 1, e); }}
}
