LeetCode-Go 题解1649. Create Sorted Array through Instructions树状数组 / 线段树计数模板实战【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读1649. Create Sorted Array through Instructions 是 LeetCode 上一道 Hard 难度的经典「动态有序数组 区间计数」问题按从左到右的顺序把元素逐个插入有序数组每次插入的代价取「严格小于」与「严格大于」当前元素的已有元素个数中的较小值最后把总代价对10^9 7取模。本文基于 LeetCode-Go 仓库中该题的完整实现先讲透题目的数学本质再分别给出**树状数组Binary Indexed Tree与线段树Segment Count Tree**两套 Go 解法并结合 template 目录下的模板源码剖析底层原理最后用仓库自带测试验证正确性。读完本文你将掌握「动态前缀计数」类问题的通用套路可迁移到逆序对、K 阶统计量等高频考题。题目原文与题意给定一个整数数组instructions要求按instructions中的元素创建一个有序数组。一开始有一个空容器nums然后从左到右遍历instructions把每个元素插入nums。每次插入的代价取下面两者的较小值nums中严格小于instructions[i]的元素个数nums中严格大于instructions[i]的元素个数。例如把元素3插入nums [1,2,3,5]时代价为min(2, 1)1、2小于35大于3插入后nums变为[1,2,3,3,5]。要求返回插入全部元素后的总最小代价由于答案可能很大需要对10^9 7即1000000007取模。注意一个关键细节与当前元素相等的已有元素既不计入「严格小于」也不计入「严格大于」这也是后面两套解法统计口径前缀区间 去重等值的由来。示例逐步推演示例 1Input: instructions [1,5,6,2] Output: 1步骤待插入值严格小于严格大于代价nums11000[1]25100[1,5]36200[1,5,6]42121[1,2,5,6]总代价0 0 0 1 1。示例 2Input: instructions [1,2,3,6,5,4] Output: 3依次插入1,2,3,6时代价均为 0插入5时代价为min(3, 1) 1插入4时代价为min(3, 2) 2总代价0 0 0 0 1 2 3。示例 3验证等值元素不计入两侧Input: instructions [1,3,3,3,2,4,2,1,2] Output: 4例如第二个3插入时nums [1,3]严格小于的有1个严格大于的有 0 个与第一个3相等的不计入任何一侧代价为min(1, 0) 0。最后一步插入2时nums [1,1,2,2,3,3,3,4]严格小于的有1,1共 2 个严格大于的有3,3,3,4共 4 个代价为min(2, 4) 2。累计得到0 0 0 0 1 0 1 0 2 4。数据约束1 instructions.length 10^51 instructions[i] 10^5核心矛盾为什么这是一道模板题约束中数组长度与元素值上限都达到10^5量级。如果对每个元素都直接遍历当前nums统计两侧数量单次插入是 O(n)整体退化为 O(n²)必然超时。因此必须把「动态维护有序集合 快速查询某个值两侧的数量」压缩到 O(log n) 以内。观察代价的两个分量严格小于v的元素个数 当前已插入的、值域在[1, v-1]区间内的元素总数严格大于v的元素个数 当前已插入总数 − 值域在[1, v]区间内的元素总数后者即「小于等于 v」的数量。于是问题被改写成维护一个值域上的计数器数组支持单点 1 插入以及前缀区间求和。这正是树状数组BIT和线段树最擅长的操作也因此原文称其为「读完题就可以判定」的模板题。原文档给出的通用四步流程Query得到strictlyLessThanQuery得到strictlyGreaterThan取两者最小值累加到答案Update把当前值计数 1。循环重复上述步骤直至全部插入完成。下面分别看两种实现。解法一树状数组Binary Indexed Tree树状数组能在 O(log n) 时间内完成「单点修改」与「前缀求和」且常数极小、代码量最少是本题的首选。核心代码完整实现见 源码文件文件名1649. Create Sorted Array through Instructions.go其核心逻辑如下// 解法一 树状数组 Binary Indexed Tree func createSortedArray(instructions []int) int { bit, res : template.BinaryIndexedTree{}, 0 bit.Init(100001) for i, v : range instructions { less : bit.Query(v - 1) greater : i - bit.Query(v) res (res min(less, greater)) % (1e9 7) bit.Add(v, 1) } return res }逐行解读bit.Init(100001)因为1 instructions[i] 10^5值域固定为[1, 100000]直接以值本身作为下标无需离散化。100001保证下标100000落在容量内内部数组长度为capacity 1。less : bit.Query(v - 1)查询前缀[1, v-1]的计数即严格小于v的元素个数。greater : i - bit.Query(v)i是当前已插入元素总数0基下标恰好等于已插入个数bit.Query(v)是小于等于v的计数两者相减得到严格大于v的元素个数。等值元素在这个减法中被自然剔除。res (res min(less, greater)) % (1e9 7)累加每次插入代价并取模防止溢出。bit.Add(v, 1)把值v的计数 1为后续查询做准备。底层模板源码解析树状数组模板定义在 template/BIT.go// BinaryIndexedTree define type BinaryIndexedTree struct { tree []int capacity int } // Init define func (bit *BinaryIndexedTree) Init(capacity int) { bit.tree, bit.capacity make([]int, capacity1), capacity } // Add define func (bit *BinaryIndexedTree) Add(index int, val int) { for ; index bit.capacity; index index -index { bit.tree[index] val } } // Query define func (bit *BinaryIndexedTree) Query(index int) int { sum : 0 for ; index 0; index - index -index { sum bit.tree[index] } return sum }关键点index -index即lowbit(x)见 template/BIT.go是树状数组的核心运算Add沿父链向上累加Query沿前缀链向下求和两者均为 O(log n)模板还提供了 InitWithNums 实现 O(n) 建树先把nums[i-1]放入tree[i]再累加到父节点ilowbit(i)以及二维树状数组BinaryIndexedTree2Dtemplate/BIT.go可用于后续扩展场景。复杂度时间每个元素 2 次Query 1 次Add整体 O(n log n)空间O(maxVal)即 O(10^5) 量级。解法二线段树Segment Count Tree当值域很大或需要区间语义更灵活的统计时可以用线段树。由于题目数据量大值域无法直接开数组覆盖时建立线段树之前要先离散化——这是原文档特别强调的一点。离散化 线段树计数完整实现见 源码文件createSortedArray1与discretization1649核心逻辑// 解法二 线段树 SegmentTree func createSortedArray1(instructions []int) int { if len(instructions) 0 { return 0 } st, res, mod : template.SegmentCountTree{}, 0, 1000000007 numsMap, numsArray, tmpArray : discretization1649(instructions) // 初始化线段树节点内的值都赋值为 0即计数为 0 st.Init(tmpArray, func(i, j int) int { return 0 }) for i : 0; i len(instructions); i { strictlyLessThan : st.Query(0, numsMap[instructions[i]]-1) strictlyGreaterThan : st.Query(numsMap[instructions[i]]1, numsArray[len(numsArray)-1]) res (res min(strictlyLessThan, strictlyGreaterThan)) % mod st.UpdateCount(numsMap[instructions[i]]) } return res } func discretization1649(instructions []int) (map[int]int, []int, []int) { tmpArray, numsArray, numsMap : []int{}, []int{}, map[int]int{} for i : 0; i len(instructions); i { numsMap[instructions[i]] instructions[i] } for _, v : range numsMap { numsArray append(numsArray, v) } sort.Ints(numsArray) for i, num : range numsArray { numsMap[num] i } for i : range numsArray { tmpArray append(tmpArray, i) } return numsMap, numsArray, tmpArray }离散化三件套的职责discretization1649返回三个对象numsMap原始值 → 离散化后的**秩rank**映射。第一轮把值塞进 map 去重排序后第二轮把下标写回 map完成「值 → 排名」压缩numsArray去重后有序的值集合用于反查最大值下标numsArray[len(numsArray)-1]tmpArray长度为去重后元素个数的索引序列[0, 1, ..., k-1]作为线段树建树的「叶子位置」。这样做的好处是即使instructions[i]上界很大本题为10^5但该写法对更大的值域同样成立线段树区间长度也只为去重元素个数空间占用被压缩到 O(k)。查询与更新语义st.Query(0, numsMap[v]-1)统计排名在[0, rank(v)-1]区间的计数即严格小于v的元素个数st.Query(numsMap[v]1, numsArray[len(numsArray)-1])统计排名在[rank(v)1, 最大排名]区间的计数即严格大于v的元素个数等值元素落在rank(v)这一档被区间排除在外st.UpdateCount(numsMap[v])把v所在档位的计数 1。注意本解法在最前面做了len(instructions) 0的兜底空数组直接返回 0避免空区间建树源码文件中SegmentCountTree.Init对空数组不做建树。底层模板源码解析线段树模板定义在 template/SegmentTree.go。本题使用的是其中的计数专用变体SegmentCountTreetemplate/SegmentTree.go它与通用SegmentTree的区别在于叶子节点存的是离散化后的排名而非原始值查询与更新都基于排名区间进行。Init复制nums到data并申请4 * len(nums)大小的tree数组线段树一般按 4 倍空间开保证最坏情况不越界Query区间求和递归时先做「完全在区间外返回 0」「完全被覆盖返回节点值」两类剪枝UpdateCount值落在[data[left], data[right]]内的节点计数 1递归至叶子后返回通用SegmentTree还额外提供Update、QueryLazy、UpdateLazy等懒标记接口template/SegmentTree.go适用于区间更新场景本文不展开。由于叶子位置从0开始节点treeIndex的左右孩子下标由 leftChild/rightChild 计算2*index1/2*index2建树与查询共用这套索引约定。复杂度时间每个元素 2 次区间查询 1 次单点更新每次 O(log k)k 为去重后元素个数整体 O(n log n)空间O(k)4 倍系数。测试验证与运行方式仓库为该题编写了表驱动测试见测试文件leetcode/1649.Create-Sorted-Array-through-Instructions/ 下1649. Create Sorted Array through Instructions_test.go测试用例与文档示例完全一致[1, 5, 6, 2]→1[1, 2, 3, 6, 5, 4]→3[1, 3, 3, 3, 2, 4, 2, 1, 2]→4[]→0空数组边界测试同时调用createSortedArray与createSortedArray1两个版本并断言结果一致因此两套解法互为验证。测试输出格式为【input】:... 【output】:...。运行方式仓库根目录go test -v -run Test_Problem1649 ./leetcode/1649.Create-Sorted-Array-through-Instructions/若想全量跑一遍所有题解并生成覆盖率报告可参考仓库根目录的 gotest.shgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本用-coverprofile对全部包一次性产出单一合法的覆盖率文件Go 1.10 特性避免了旧写法合并多个 profile 时头部格式不合法的问题。总结与扩展两道解法本质上是同一套「动态前缀计数」模型的两个载体树状数组代码极简、常数小值域固定时如本题10^5甚至免离散化是竞赛与面试的首选线段树SegmentCountTree语义更通用值域大或需要区间级操作时配合离散化使用模板本身还支持懒标记区间更新。该模型的适用面很广逆序对计数、K 阶统计量查询第 k 小、在线众数/中位数、区间内不同元素个数等题目都可以复用 template/BIT.go 与 template/SegmentTree.go 中的模板。掌握「严格小于 前缀区间求和」「严格大于 总数 − 前缀区间求和」这两个转换加上对等值元素区间边界的处理就能以不变应万变。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考