重庆市建设医院网站wordpress 链接打不开

题目描述与示例

题目描述

小欧拿到了一个数组，她有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(N+q)。第一次计算nums的和的时间复杂度为O(N)，进行q次修改的时间复杂度为O(q)

空间复杂度：O(1)。仅需若干常数变量。

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多