2024-09-18：用go语言，给定一个从 0 开始的长度为 n 的正整数数|下标|复杂度|整数|调用

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.初始化变量：给定数组和二维数组，创建一个长度为的数组，其中是数组的长度。初始化为 0。

nums

queries

ids

nums

2.遍历数组，同时计算数组元素的和，并将每个元素的索引存入数组中。

nums

ids

3.对数组进行稳定排序，排序依据是对应元素在中的值。

ids

nums

4.创建一个答案数组，长度为的长度，用于存储每次操作后未标记元素的和值。

ans

queries

5.遍历数组，对每个操作进行处理：

queries

•获取操作指令中的下标和数值。
i
k
•更新当前和，减去下标对应的元素值并将其置为 0，表示已标记。
s
i
•在已排序的中找到最小值且未标记的元素进行标记，标记数量为。更新和对应元素值为 0。
ids
k
s
•将当前未标记元素的和值存入答案数组中。
s
ans

6.返回答案数组。

ans

总的时间复杂度：

•初始化和遍历数组、对数组排序、处理每个查询操作都需要 O(n log n) 的时间。
nums
ids
•所以总的时间复杂度为 O(n log n) + O(m * log n)，其中是数组的长度，是的长度。
n
nums
m
queries

总的额外空间复杂度：

•需要额外的空间来存储、数组，以及函数调用栈的空间等。
ids
ans
•、数组的长度分别为和，额外空间复杂度为 O(n + m)。
ids
ans
n
m
•函数调用栈的空间复杂度为 O(1)。
•所以总的额外空间复杂度为 O(n + m)。

Go完整代码如下：

packagemain
import(
"fmt"
"slices"
)
funcunmarkedSumArray(nums[]int,queries[][]int)[]int64{
s,n:=0,len(nums)
ids:=make([]int,n)
fori,x:=rangenums{
s+=x
ids[i]=i
}
slices.SortStableFunc(ids,func(i,jint)int{returnnums[i]-nums[j]})
ans:=make([]int64,len(queries))
j:=0
forqi,p:=rangequeries{
i,k:=p[0],p[1]
s-=nums[i]
nums[i]=0//标记
for;j0;j++{
i:=ids[j]
ifnums[i]>0{//没有被标记
s-=nums[i]
nums[i]=0
k--
}
}
ans[qi]=int64(s)
}
returnans
}
funcmain(){
nums:=[]int{1,2,2,1,2,3,1}
queries:=[][]int{{1,2},{3,3},{4,2}}
fmt.Println(unmarkedSumArray(nums,queries))
}

Rust完整代码如下：

fnunmarked_sum_array(mutnums:Vec,queries:Vec>)->Vec{
letn=nums.len();
letmutids:Vec=(0..n).collect();
ids.sort_by(|&i,&j|nums[i].cmp(&nums[j]));
letmuts=nums.iter().sum::();
letmutans=Vec::new();
letmutj=0;
forpinqueries{
letqi=p[0]asusize;
letmuti=p[1]asusize;
s-=nums[i];
nums[i]=0;
whilej0{
letidx=ids[j];
ifnums[idx]>0{
s-=nums[idx];
nums[idx]=0;
i-=1;
}
j+=1;
}
ans.push(sasi64);
}
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));
}