高唐建筑公司网站,有了域名如何建网站,教育类型网站,网页设计图片欣赏题目描述与示例
题目描述
小欧拿到了一个数组#xff0c;她有q次操作#xff0c;每次操作修改一个元素。小欧希望每次修改后得到当前数组所有元素之和。你能帮帮她吗#xff1f;
输入描述
第一行输入两个正整数n和q#xff0c;代表数组的大小和操作次数。
第二行输入n…题目描述与示例
题目描述
小欧拿到了一个数组她有q次操作每次操作修改一个元素。小欧希望每次修改后得到当前数组所有元素之和。你能帮帮她吗
输入描述
第一行输入两个正整数n和q代表数组的大小和操作次数。
第二行输入n个正整数ai代表小欧拿到的初始数组。
接下来的q行每行输入两个正整数i和x代表将第i个元素修改为x。
输出描述
输出q行每行输出一个正整数代表当前数组元素之和。
示例
输入
5 3
1 2 3 4 5
2 3
3 3
5 1输出
16
16
12说明
第一次修改后数组变成[1,3,3,4,5]元素之和为16。
第二次修改后数组变成[1,3,3,4,5]元素之和为16。
第三次修改后数组变成[1,3,3,4,1]元素之和为12。
解题思路
本题属于非常简单的模拟题。
对于某一次特定的修改假设我们已知上一次修改后的数组和为nums_sum而本次修改将nums[i]修改为x那么修改后的和应该为nums_sum-nums[i]x。而此处修改后的和又可以作为下一次修改的上一次修改后的数组和来使用即存在
nums_sum nums_sum - nums[i] x需要被在本次修改后输出。同时nums[i]需要修改为x。上述核心代码为
nums_sum - nums[i]
nums_sum x
nums[i] x本题要特别注意题目最后q行输入的索引值是从1开始的故映射到数组的索引值必须进行i - 1的修改。
代码
Python
# 题目【模拟】OPPO2023秋招提前批-小欧数组求和
# 作者闭着眼睛学数理化
# 算法模拟
# 代码有看不懂的地方请直接在群上提问# 数组长度n操作次数q
n, q map(int, input().split())
# 初始数组nums
nums list(map(int, input().split()))
# 计算初始数组nums的和
nums_sum sum(nums)
# 储存q次修改的结果
ans list()# 循环q次修改q次
for _ in range(q):# 修改的位置i和修改的内容xi, x map(int, input().split())# 注意i输入表示的是第i个元素将其改为索引需要-1i - 1# 将nums[i]修改为x则整体的和需要减少nums[i]增加xnums_sum - nums[i]nums_sum x# 同时nums[i]被修改为xnums[i] x# 将本次修改后的数组和nums_sum储存在ans中方便后续按顺序输出ans.append(nums_sum)for num in ans:print(num)Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int q scanner.nextInt();int[] nums new int[n];for (int i 0; i n; i) {nums[i] scanner.nextInt();}int numsSum 0;for (int num : nums) {numsSum num;}int[] ans new int[q];for (int k 0; k q; k) {int i scanner.nextInt() - 1;int x scanner.nextInt();numsSum - nums[i];numsSum x;nums[i] x;ans[k] numsSum;}for (int num : ans) {System.out.println(num);}}
}C
#include iostream
using namespace std;int main() {int n, q;cin n q;int nums[n];for (int i 0; i n; i) {cin nums[i];}int numsSum 0;for (int i 0; i n; i) {numsSum nums[i];}int ans[q];for (int k 0; k q; k) {int i, x;cin i x;i--;numsSum - nums[i];numsSum x;nums[i] x;ans[k] numsSum;}for (int i 0; i q; i) {cout ans[i] endl;}return 0;
}时空复杂度
时间复杂度O(Nq)。第一次计算nums的和的时间复杂度为O(N)进行q次修改的时间复杂度为O(q)
空间复杂度O(1)。仅需若干常数变量。
华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务100同学成功上岸 课程讲师为全网50w粉丝编程博主吴师兄学算法 以及小红书头部编程博主闭着眼睛学数理化 每期人数维持在20人内保证能够最大限度地满足到每一个同学的需求达到和1v1同样的学习效果 60天陪伴式学习40直播课时300动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 OD算法冲刺训练课程表 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
