企业官网建设流程全解析

• 科学计算

本文围绕 LeetCode 第 126 场双周赛 B 题（编号 3080，Mark Elements on Array by Performing Queries）展开，完整讲解"按值从小到大的索引排序 + 标记即清零"的核心思路，并给出 Python3 / Java / C++ / Go 四种语言实现、复杂度分析，以及 codeforces-go 仓库中该题对应的测试驱动与样例验证，读者学完后可独立复现并推广该技巧到同类"按顺序选择最小未处理元素"的问题中。

题目背景与核心矛盾

题意可以概括为：给定正整数数组nums和若干查询queries，每个查询给出(index, k)，先标记nums[index]，再额外标记当前 k 个最小的、尚未被标记的元素，每次查询结束后返回"剩余未标记元素之和"。

这道题的核心矛盾在于：

• 要"按照元素值从小到大"挑选未标记元素，直觉上需要排序；
• 但查询又要求针对特定下标index做标记，不能直接对nums排序（排序会破坏下标与值的对应关系）。

解决方案是经典的排序索引（index sort）手法：额外创建一个ids数组，令ids[i] = i，然后按nums[ids[i]]从小到大对ids排序。这样既得到了"值从小到大的全局顺序"，又保留了下标信息用于回答特定index的标记操作。

核心思路拆解：索引稳定排序 + 标记清零

预处理：构造有序索引

ids = sorted(range(n), key=lambda i: nums[i])

注意这里必须使用稳定排序（stable sort）：

• 对于值相同的元素，排序后它们的下标依然按照下标从小到大排列；
• 若使用不稳定排序（如快速排序），则必须显式在比较函数中加入"值相同按下标从小到大"的次级规则。

从仓库的 Go 实现可以看到这一细节的落地：b.go 中使用了 Go 1.21 的slices.SortStableFunc：

slices.SortStableFunc(id, func(i, j int) int { return nums[i] - nums[j] })

SortStableFunc保证比较结果相等的元素保持原始相对顺序，恰好满足"相同值按下标从小到大"的需求，这也是为什么模板库作者在 copypasta/common.go 等泛型排序场景中同样偏好稳定排序的原因（该文件第 2461 行附近的注释即标注了"or SortStableFunc"的等价写法）。

标记 = 清零：利用正整数性质免去哈希表

题目保证nums中元素都是正数，因此可以做一个精妙的简化：

• 初始化s为nums元素之和；
• 标记一个数就是把它置为 0，同时在s中减去它的值；
• 判断"是否已被标记"只需检查nums[i] > 0（0 表示已标记）。

这样无需额外的visited数组或哈希表，空间更省、判断更快。

每轮查询的处理流程

设ids已按值升序排好，维护一个只前进不回溯的指针j（初始为 0）：

1. 标记指定下标：s -= nums[index]，然后nums[index] = 0；
2. 标记 k 个最小未标记元素：从j开始沿ids扫描，跳过已被标记的（值为 0）元素，遇到未标记的（值 > 0）就清零并累计减去；指针j始终单调递增，因此整个流程中每个下标最多被扫描一次；
3. 记录当前s作为本次查询的答案。

指针j的单调性是该算法能从"每轮从头找 k 个最小"的 O(n·q) 降到 O(n log n) 的关键：ids已经全局有序，被标记过的元素只会越来越多，游标只会向右移动。

多语言实现（原文完整继承）

以下四种语言实现完全等价，均来自原解题文档。

Python3

class Solution: def unmarkedSumArray(self, nums: List[int], queries: List[List[int]]) -> List[int]: n = len(nums) s = sum(nums) ids = sorted(range(n), key=lambda i: nums[i]) # 稳定排序 ans = [] j = 0 for i, k in queries: s -= nums[i] nums[i] = 0 # 标记 while j < n and k: i = ids[j] if nums[i]: # 没有被标记 s -= nums[i] nums[i] = 0 k -= 1 j += 1 ans.append(s) return ans

Python 的sorted是稳定排序，配合key=lambda i: nums[i]即可得到"值升序、同值按下标升序"的索引序列。

Java

class Solution { public long[] unmarkedSumArray(int[] nums, int[][] queries) { int n = nums.length; long s = 0; Integer[] ids = new Integer[n]; for (int i = 0; i < n; i++) { s += nums[i]; ids[i] = i; } Arrays.sort(ids, (i, j) -> nums[i] - nums[j]); // 稳定排序 long[] ans = new long[queries.length]; int j = 0; for (int qi = 0; qi < queries.length; qi++) { int[] q = queries[qi]; int i = q[0]; int k = q[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] = s; } return ans; } }

注意 Java 中nums[i] - nums[j]作为比较器时，若差值可能溢出（本题值域内安全）需改用Integer.compare；同时返回值必须用long[]承接可能超过 int 范围的元素和。

C++

class Solution { public: vector<long long> unmarkedSumArray(vector<int> &nums, vector<vector<int>> &queries) { int n = nums.size(); long long s = accumulate(nums.begin(), nums.end(), 0LL); vector<int> ids(n); iota(ids.begin(), ids.end(), 0); ranges::stable_sort(ids, & { return nums[i] < nums[j]; }); vector<long long> ans; int j = 0; for (auto &q : queries) { int i = q[0], k = q[1]; s -= nums[i]; nums[i] = 0; // 标记 for (; j < n && k; j++) { i = ids[j]; if (nums[i] > 0) { // 没有被标记 s -= nums[i]; nums[i] = 0; k--; } } ans.push_back(s); } return ans; } };

C++20 的ranges::stable_sort直接支持稳定排序；iota用于快速生成0..n-1的索引序列。

Go（仓库工程化版本）

func unmarkedSumArray(nums []int, queries [][]int) []int64 { s, n := 0, len(nums) id := make([]int, n) for i, x := range nums { s += x id[i] = i } slices.SortStableFunc(id, 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 := id[j] if nums[i] > 0 { // 没有标记 s -= nums[i] nums[i] = 0 k-- } } ans[qi] = int64(s) } return ans }

复杂度分析

• 时间复杂度：O(n log n)，其中 n 为nums的长度。瓶颈在排序上；排序之后，每轮查询中指针j单调右移，全部查询对ids的总扫描次数不超过 n。
• 空间复杂度：O(n)（忽略返回值空间）。ids数组占用 O(n)；其余变量为常数空间。

由于j不回溯，即使有 q 个查询，标记"k 个最小未标记元素"的总代价仍为 O(n)，这正是该解法在 n、q 均达到较大规模时依然高效的原因。

仓库中的工程化落地：测试驱动与样例验证

本题在 codeforces-go 仓库中不是孤立的一段代码，而是被完整的 LeetCode 测试流水线覆盖，可用于本地复现验证。

目录结构与三个文件的分工

leetcode/biweekly/126/b/目录下共四个文件：

• README.md：原解题文档（即本文主体内容来源）；
• b.go：解法实现，即上文 Go 版本；
• b.txt：测试用例数据文件；
• b_test.go：测试入口。

其中 b_test.go 的测试驱动如下：

func Test_b(t *testing.T) { if err := testutil.RunLeetCodeFuncWithFile(t, unmarkedSumArray, "b.txt", 0); err != nil { t.Fatal(err) } } // https://leetcode.cn/contest/biweekly-contest-126/problems/mark-elements-on-array-by-performing-queries/ // https://leetcode.cn/problems/mark-elements-on-array-by-performing-queries/

RunLeetCodeFuncWithFile定义在 leetcode/testutil/leetcode.go：它读取b.txt，去掉空行后按"输入行数 = 函数入参个数 + 出参个数"的规则切分测试数据，再借助反射（parseRawArg/toRawString）将文本自动解析为 Go 类型并逐条比对输出，同时支持 TLE 检测（超时阈值在 leetcode/testutil/config.go 中默认为2 * time.Second）。这套机制让"每场周赛/双周赛题目落地为可回归的测试用例"变成流水线操作——双周赛测试的批量生成入口见 copypasta/template/leetcode/generator_test.go 中的TestBiweekly。

用 b.txt 中的样例做逐步推演

b.txt包含两组用例，第一组（原文注释未给出推导，这里补全）为：

nums = [1,2,2,1,2,3,1] # s = 12 queries = [[1,2],[3,3],[4,2]] answer = [8,3,0]

• ids稳定排序后为[0,3,6,1,2,4,5]（值为 1 的三个下标 0/3/6 排最前，且按下标升序）；
• 查询[1,2]：先标记下标 1（值 2），s = 10；再按 ids 依次标记下标 0（值 1）与下标 3（值 1），s = 8；
• 查询[3,3]：下标 3 已被标记（值 0），s不变仍为 8；指针继续沿 ids 扫描，依次标记下标 6（值 1）、下标 2（值 2）、下标 4（值 2），s = 3；
• 查询[4,2]：下标 4 已是 0；ids 中剩余未标记的只有下标 5（值 3），标记后s = 0。

第二组用例[1,4,2,3]+[[0,1]]则验证了"目标下标恰好也是最小元素"的情形：先标记下标 0（值 1），随后沿 ids 标记的仍是下标 0（已被标记则跳过）与下标 2（值 2），最终s = 7。

边界情况与易错点小结

• 稳定排序的必要性：相同值的下标必须按下标从小到大标记，直接快排会破坏该约束；若用不稳定排序必须补次级比较条件（值相同比下标）。
• "清零即标记"依赖正整数前提：若数组允许负数或 0，该技巧失效，需要引入visited数组。
• 指针 j 的推进位置：无论当前ids[j]是否已被标记，j都要自增，否则死循环；外层还需j < n防越界（当所有元素都被标记后，k 可能仍大于 0，此时直接结束循环）。
• 求和溢出：Java / C++ / Go 的实现均使用 64 位整数（long/long long/int64）承载元素和，避免大测试数据下 int 溢出。

延伸：相关题单主题

该解法属于"按顺序处理最小未标记元素"的通用技巧。原文档附带的相关题单主题包括：滑动窗口（定长/不定长/多指针）、二分算法（二分答案/最小化最大值/最大化最小值/第 K 小）、单调栈（矩形系列/字典序最小/贡献法）、网格图（DFS/BFS/综合应用）、位运算（基础/性质/拆位/试填/恒等式/贪心/脑筋急转弯）、图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）等（原文档以链接形式给出，读者可按需在个人主页讨论区检索对应合集）。将"索引排序 + 单调指针"的模式迁移到这些场景中，往往能让"每次取当前最小未处理项"类问题的时间复杂度从 O(nq) 降到 O(n log n)。

• 科学计算