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完整代码如下：package mainimport ( "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完整代码如下：fn unmarked_sum_array(mut nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i64> { let n = nums.len(); let mut ids: Vec<usize> = (0..n).collect(); ids.sort_by(|&i, &j| nums[i].cmp(&nums[j])); let mut s = nums.iter().sum::<i32>(); let mut ans = Vec::new(); let mut j = 0; for p in queries { let qi = p[0] as usize; let mut i = p[1] as usize; s -= nums[i]; nums[i] = 0; while j < n && i > 0 { let idx = ids[j]; if nums[idx] > 0 { s -= nums[idx]; nums[idx] = 0; i -= 1; } j += 1; } ans.push(s as i64); } ans}fn main() { let nums = vec![1, 2, 2, 1, 2, 3, 1]; let queries = vec![vec![1, 2], vec![3, 3], vec![4, 2]]; println!("{:?}", unmarked_sum_array(nums, queries));}