科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文以 LeetCode 周赛 192 的 A 题「重新排列数组Shuffle the Array1470」为切入点完整讲解两种解法O(n) 额外空间的「创建新数组」与 O(1) 额外空间的「置换环原地交换」并结合算法竞赛模板库 codeforces-go 中该题对应的 Go 源码实现 与 单元测试用例从源码级验证两种算法的正确性。读完本文你将掌握「双指针线性填充」与「利用置换环 符号位标记访问」两类经典数组重排技巧并能直接在本仓库的周赛目录结构中复现与扩展这类题解。题目概述与问题背景题目要求给定数组nums它由x1, x2, ..., xn, y1, y2, ..., yn构成即前 n 个元素与后 n 个元素分别构成两段。请重新排列数组使其变为[x1, y1, x2, y2, ..., xn, yn]并返回该新数组。本题出现在本仓库的周赛归档目录 leetcode/weekly/192/ 中对应 2020 年 6 月的力扣第 192 场周赛 A 题同场次的 B/C/D 题如 1472.md 的浏览器历史记录设计题也归档在相邻目录中方便整套周赛复盘。归档结构遵循本仓库统一的「题目编号 题解 md 解法源码 测试文件」模式详见下文。方法一创建新数组双指针线性填充这是最直观、最容易写对的解法时间复杂度 O(n)空间复杂度 O(n)。算法过程创建一个长为 2n 的数组ans作为答案。根据题意对于 i 0, 1, ..., n-1把nums[i]前半段第 i 个元素填入ans[2i]偶数下标把nums[ni]后半段第 i 个元素填入ans[2i1]奇数下标。本质上是「两个指针 一个目标下标」的线性扫描指针 i 同时遍历前、后两段写入位置每次 2。各语言实现要点原题解文档给出了 Python3 / Java / C / C / Go / JavaScript / Rust 七种语言的等价实现。核心差异仅在语法层面Python3ans [0] * (2 * n)预分配然后ans[i * 2] nums[i]; ans[i * 2 1] nums[n i]。Java / C以n * 2为长度构造新数组循环内同样按2i与2i1双写。C需要额外通过*returnSize输出数组长度*returnSize n * 2;由调用方负责释放malloc的内存。Go本仓库中的实现 a.gofunc shuffle1(nums []int, n int) []int { ans : make([]int, n*2) for i, x : range nums[:n] { ans[i*2] x ans[i*21] nums[ni] } return ans }这里用range nums[:n]直接迭代前半段切片配合nums[ni]取后半段元素写法比按下标循环更简洁同时make([]int, n*2)保证了写入ans[i*21]时下标不越界当 i n-1 时i*21 2n-1 恰好是数组最后一个下标。JavaScriptconst ans Array(n * 2);预留长度后按位写入。Rust注意n是i32需要先let n n as usize;再用于切片下标与vec![0; n * 2]。复杂度分析时间复杂度O(n)单趟循环完成全部 2n 个元素的填入。空间复杂度O(n)额外的新数组ans。方法二原地交换置换环 符号位标记方法二把空间复杂度压缩到 O(1)核心思想是把下标变换看成置换利用置换环一次性归位所有元素。这是本文最有价值的进阶技巧。下标变换的置换结构设 f(i) 为「下标 i 处的元素在答案中的下标」。由题意若 i n前半段则 f(i) 2i若 i n后半段则 f(i) (i - n) * 2 1。原题解以 n 4 为例给出了完整的环结构nums[0]的目标就是 0不变环 11 → 2 → 4 → 1即nums[1]移到下标 2nums[2]移到下标 4nums[4]移到下标 1环 23 → 6 → 5 → 3nums[7]的目标就是 7不变。示例 2 的nums [1,2,3,4,4,3,2,1]按上述过程执行结果为[1,4,2,3,3,2,4,1]与官方示例输出完全一致该用例同样收录在仓库测试文件中见下文。如何判断元素是否已访问如果按朴素思路用布尔数组vis记录访问过的下标额外空间依然是 O(n)与方法一无异。原题解给出了一个更省空间的巧妙做法本题nums[i]都是正数可以把访问过的数加个负号变成相反数当作「已访问」标记。遍历到一个负数时直接跳过最后把所有数取反复原成正数即为答案。具体流程遍历nums跳过值为负数的下标已被标记过从当前下标cur i出发反复计算目标下标nxt cur n ? cur * 2 : (cur - n) * 2 1若nxt i说明走完了一个环把当前元素取负写回nums[i]后 break否则把当前元素 x 填入nums[nxt]写入负数-x以标记访问同时把nums[nxt]原来的值正值作为新的 x 继续走环全部环处理完后把数组整体取反复原。答疑为什么每个元素恰好被标记一次原题解附带了一个关键答疑值得单独强调问这个做法是否会把一个元素标记多次取反多次或者有元素没有被标记答设 f(i) 是下标为 i 的元素在答案中的下标。根据题意f 是[0, 1, 2, ..., 2n-1]的一个置换。由于置换可以拆分成若干个环所以每个元素恰好被标记一次。这解释了算法正确性置换的环分解保证「从任意未访问元素出发沿 f 走必然回到起点并恰好覆盖环上所有元素一次」从而既不会漏标也不会重复取反。Go 实现本仓库 a.gofunc shuffle(nums []int, n int) []int { for i, x : range nums { if x 0 { // 已访问 continue } for cur : i; ; { // 元素 x 要填入 nums[nxt] nxt : cur * 2 if cur n { nxt (cur-n)*2 1 } if nxt i { // 回到起点 nums[i] -x // 用负数表示访问过 break } // 把 x 填入 nums[nxt]用负数表示访问过 // 同时把原来位于 nxt 的数记为 x x, nums[nxt] nums[nxt], -x cur nxt } } // 复原 for i, x : range nums { nums[i] -x } return nums }注意 Go 版本在计算nxt时没有使用三目运算符而是用if cur n分支这是 Go 语法限制下的等价写法。Python、Java、C、C、JavaScript 版本逻辑完全一致其中 C 使用swap(x, nums[nxt])后对nums[nxt]取负语义相同。复杂度分析时间复杂度O(n)。虽然代码看起来是二重循环外层遍历 内层走环但每个元素「被标记为负数」只会发生恰好一次内层循环在所有环上的总步数之和为 n因此总循环次数是 O(n)。空间复杂度O(1)只使用若干临时变量复用原数组完成重排。仓库源码与测试验证解法源码的归档形态本题解在仓库中以「题解 实现 测试」三位一体的方式归档在 leetcode/weekly/192/a/ 目录1470.md本文讲解的完整题解文档方法一 方法二 答疑 相似题目a.go包含shuffle1方法一与shuffle方法二两个实现函数签名与力扣要求的func shuffle(nums []int, n int) []int一致a_test.go自动生成的单元测试。同名文件a.go中同时保留两种解法且注释直接引用题解中的「已访问 / 回到起点」标记逻辑代码与 1470.md 的算法描述一一对应便于对照阅读。测试用例与运行方式a_test.go 由仓库的测试生成器copypasta/template/leetcode/generator_test.go自动生成其测试数据覆盖了力扣官方全部示例输入 numsn期望输出[2,5,1,3,4,7]3[2,3,5,4,1,7][1,2,3,4,4,3,2,1]4[1,4,2,3,3,2,4,1][1,1,2,2]2[1,2,1,2][0,1,2,3,4,5]3[0,1,2,3,4,5][0,1,2,3,4,5,6,7]4[0,1,2,3,4,5,6,7]后两组「输入恰好是答案」的用例很有价值它们专门用来验证原地算法不会破坏已有序的数组例如 n4 时[0,1,2,3,4,5,6,7]的每个环都是自环元素本就该留在原位若环处理逻辑有误如重复取反就会立刻暴露。测试调用的是仓库统一的测试框架testutil.RunLeetCodeFuncWithExamples定义于 leetcode/testutil/leetcode.go该框架通过反射解析测试数据examples每行的前 fNumIn 个字符串作为输入、后 fNumOut 个作为期望输出自动完成类型解析parseRawArg支持 int、slice、string、TreeNode 等类型与结果比对assert.Equal。运行方式为标准 Go 测试命令go test ./leetcode/weekly/192/a/ -run Test_a -v测试框架还内置了超时检测DebugTLE默认 2 秒见 leetcode/testutil/config.go与答案错误提示targetCaseNum : 0表示跑全部用例改为正数可只跑指定用例改为-1则跑最后一个用例。测试框架与周赛归档流水线理解测试文件的开头注释「Code generated by copypasta/template/leetcode/generator_test.go」能帮你更好地利用本仓库仓库作者通过 generator_test.go 中的TestWeekly/TestBiweekly自动获取下一场周赛/双周赛的题目信息登录使用环境变量LEETCODE_USERNAME_ZH、LEETCODE_PASSWORD_ZH可自定义LEETCODE_COMMENT注释自动生成a.go、a_test.go与测试数据并按leetcode/weekly/场次/题号/的约定归档。这意味着每周赛题发布后题解、实现与测试会被一次性补齐——本文分析的 1470.md 正是这一流水线的产物之一。相似题目与延伸原题解末尾给出了两道思路相近的经典题目可用于巩固「置换 / 排列类数组操作」这一主题1920. 基于排列构建数组同样是「按下标重排数组」的直接应用用新数组或原地技巧均可解。41. 缺失的第一个正数经典原地哈希题同样依赖「把数组元素的值作为下标信息、用正负号标记状态」的思想与本题「负数标记已访问」异曲同工。从这两道题可以提炼出一个通用套路当题目要求数组重排、去重或状态标记且元素值域允许「符号翻转」或「取负取反」时常可以用符号位代替 O(n) 的辅助数组把空间复杂度压到 O(1)。这也是排列、置换环、原地哈希一类题目的核心考点。小结围绕「重新排列数组」这道周赛 A 题本文完整覆盖了原题解文档的两个解法方法一创建新数组双指针线性填充O(n) 时间、O(n) 空间逻辑直白、最适合作为保底写法方法二原地交换将下标变换视作置换、沿环归位元素并用「负数标记访问」省去 vis 数组O(n) 时间、O(1) 空间是值得反复体会的进阶技巧配合仓库中 a.go 的源码与 a_test.go 的 5 组测试用例两种算法均可在本地直接验证。掌握「置换环 符号位标记」后你不只能 AC 这一道题还能将其迁移到缺失的第一个正数、数组轮转、原地哈希等一系列排列类问题中这也是本仓库将题解、源码与测试统一归档的价值所在。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐把数组当栈与双指针交换LeetCode 283 移动零的两种原地解法精讲codeforces-go 仓库题解把数组当栈与双指针交换LeetCode 283 移动零的两种原地解法精讲codeforces go 仓库题解 导读 本文围绕本仓库题解文档 leetcod科学计算LogicStack-LeetCode 刷穿 LeetCode1470. 重新排列数组简单—— 双指针模拟的入门范本LogicStack LeetCode 刷穿 LeetCode1470. 重新排列数组简单—— 双指针模拟的入门范本 本篇题解以 LogicStack L教程文档LeetCode-Go 第 27 题 Remove Element原地删除数组元素的交换双指针解法与全量测试验证LeetCode Go 第 27 题 Remove Element原地删除数组元素的交换双指针解法与全量测试验证 本篇基于 LeetCode Go 仓库中 l示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考