全面的基础微网站开发,如何注册网络公司,网络seo推广培训,专业网站建设制作价格Problem: 797. 差分 文章目录 思路解题方法复杂度Code 思路 这是一个差分数组的问题。差分数组的主要适用场景是频繁对原始数组的某一个区间进行增减操作。这种操作是区间修改操作#xff0c;在这种操作下#xff0c;差分数组只需要对区间的两个端点进行操作#xff0c;时间… Problem: 797. 差分 文章目录 思路解题方法复杂度Code 思路 这是一个差分数组的问题。差分数组的主要适用场景是频繁对原始数组的某一个区间进行增减操作。这种操作是区间修改操作在这种操作下差分数组只需要对区间的两个端点进行操作时间复杂度为O(1)。 在这个问题中我们需要对数组的某个区间进行加法操作然后输出修改后的数组。我们可以使用差分数组来解决这个问题。 解题方法 1.首先我们需要将原始数组转换为差分数组。差分数组的第i个数等于原始数组的第i个数和第i-1个数的差值。 2.然后对于每一个操作我们只需要将差分数组的左端点加上c右端点后一个位置减去c。 3.最后我们将差分数组转换回原始数组即可得到结果。 复杂度
时间复杂度: O ( n ) O(n) O(n)其中n是数组的长度。我们需要遍历一次数组来构建差分数组然后遍历一次差分数组来得到结果。 空间复杂度: O ( n ) O(n) O(n)我们需要额外的空间来存储差分数组。 Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in); static int MAXN 100010;static int[] arr new int[MAXN];static int[] dif new int[MAXN];static int n, m;public static void main(String[] args) throws IOException {n nextInt();m nextInt();for(int i 1; i n; i) {arr[i] nextInt();}while(m-- 0) {int l nextInt();int r nextInt();int c nextInt();dif[l] c;dif[r 1] - c;}for(int i 1; i n; i) {dif[i] dif[i - 1];out.print(arr[i] dif[i]);out.print( );}out.flush();}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}
