2024-09-18：用go语言，给定一个从 0 开始的长度为 n 的正整数数组 nums 和一个二维操作数组 queries，每个操作由一个下标值 indexi 和一个数值 ki 组成。
开始时，数组中的所有元素都是未标记的。依次执行 m 次操作，每次操作的过程如下：
1.如果下标 indexi 对应的元素还未标记，则标记这个元素。
2.然后再标记数组中最小的未标记元素，标记 ki 个。如果有多个值相等的未标记元素，优先标记下标较小的。若未标记元素不足 ki 个，则将它们全部标记。
我们需要返回一个长度为 m 的数组 answer，其中 answer[i] 表示执行第 i 次操作后，数组中未标记元素的和值。
输入：nums = [1,2,2,1,2,3,1], queries = [[1,2],[3,3],[4,2]]。
输出：[8,3,0]。
解释：
我们依次对数组做以下操作：
标记下标为 1 的元素，同时标记 2 个未标记的最小元素。标记完后数组为 nums = [1,2,2,1,2,3,1] 。未标记元素的和为 2 2 3 1 = 8 。
标记下标为 3 的元素，由于它已经被标记过了，所以我们忽略这次标记，同时标记最靠前的 3 个未标记的最小元素。标记完后数组为 nums = [1,2,2,1,2,3,1] 。未标记元素的和为 3 。
标记下标为 4 的元素，由于它已经被标记过了，所以我们忽略这次标记，同时标记最靠前的 2 个未标记的最小元素。标记完后数组为 nums = [1,2,2,1,2,3,1] 。未标记元素的和为 0 。
答案2024-09-18：
chatgpt
题目来自leetcode3080。
大体步骤如下：
1.初始化变量：给定 nums 数组和 queries 二维数组，创建一个长度为 n 的 ids 数组，其中 n 是 nums 数组的长度。初始化 s 为 0。
2.遍历 nums 数组，同时计算数组元素的和 s，并将每个元素的索引存入 ids 数组中。
3.对 ids 数组进行稳定排序，排序依据是对应元素在 nums 中的值。
4.创建一个答案数组 ans，长度为 queries 的长度，用于存储每次操作后未标记元素的和值。
5.遍历 queries 数组，对每个操作进行处理：
- • 获取操作指令中的下标
i和数值k。 - • 更新当前和
s，减去下标i对应的元素值并将其置为 0，表示已标记。 - • 在已排序的
ids中找到最小值且未标记的元素进行标记，标记数量为k。更新s和对应元素值为 0。 - • 将当前未标记元素的和值
s存入答案数组ans中。
6.返回答案数组 ans。
总的时间复杂度：
- • 初始化和遍历
nums数组、对ids数组排序、处理每个查询操作都需要 O(n log n) 的时间。 - • 所以总的时间复杂度为 O(n log n) O(m * log n)，其中
n是nums数组的长度，m是queries的长度。
总的额外空间复杂度：
- • 需要额外的空间来存储
ids、ans数组，以及函数调用栈的空间等。 - •
ids、ans数组的长度分别为n和m，额外空间复杂度为 O(n m)。 - • 函数调用栈的空间复杂度为 O(1)。
- • 所以总的额外空间复杂度为 O(n m)。
Go完整代码如下：
代码语言：javascript复制package main
import(
"fmt"
"slices"
)
func unmarkedSumArray(nums []int, queries [][]int)[]int64{
s, n :=0,len(nums)
ids :=make([]int, n)
for i, x :=range nums {
s = x
ids[i]= i
}
slices.SortStableFunc(ids,func(i, j int)int{return nums[i]- nums[j]})
ans :=make([]int64,len(queries))
j :=0
for qi, p :=range queries {
i, k := p[0], p[1]
s -= nums[i]
nums[i]=0// 标记
for; j < n && k >0; j {
i := ids[j]
if nums[i]>0{// 没有被标记
s -= nums[i]
nums[i]=0
k--
}
}
ans[qi]=int64(s)
}
return ans
}
func main(){
nums :=[]int{1,2,2,1,2,3,1}
queries :=[][]int{{1,2},{3,3},{4,2}}
fmt.Println(unmarkedSumArray(nums, queries))
}
Rust完整代码如下：
代码语言：javascript复制fn unmarked_sum_array(mut nums:Vec<i32>, queries:Vec<Vec<i32>>)->Vec<i64>{
letn= nums.len();
letmut ids:Vec<usize>=(0..n).collect();
ids.sort_by(|&i,&j| nums[i].cmp(&nums[j]));
letmut s= nums.iter().sum::<i32>();
letmut ans=Vec::new();
letmut j=0;
forpin queries {
letqi= p[0]asusize;
letmut i= p[1]asusize;
s -= nums[i];
nums[i]=0;
while j < n && i >0{
letidx= ids[j];
if nums[idx]>0{
s -= nums[idx];
nums[idx]=0;
i -=1;
}
j =1;
}
ans.push(s asi64);
}
ans
}
fnmain(){
letnums=vec![1,2,2,1,2,3,1];
letqueries=vec![vec![1,2],vec![3,3],vec![4,2]];
println!("{:?}",unmarked_sum_array(nums, queries));
}
