LeetCode 1649. 通过指令创建有序数组：二分模拟、计数线段树与代价最小化题解

LeetCode 1649. 通过指令创建有序数组二分模拟、计数线段树与代价最小化题解【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文基于开源仓库 leetcodeLeetCode 题解集中 problems/1649.create-sorted-array-through-instructions.md 展开完整讲解 LeetCode 1649「通过指令创建有序数组」的题目背景、两类经典解法二分插入模拟、计数线段树及其复杂度权衡。读完本文你将掌握如何将动态插入 统计小于/大于数量的模型转化为可编码的算法理解 Python 切片插入与list.insert的性能差异以及线段树区间计数模板的写法与适用边界。题目回顾有序数组上的最小插入代价问题描述给定一个整数数组instructions需要根据其中的元素从左到右创建一个有序数组nums。初始nums为空每次将instructions[i]插入nums时代价为以下两者的较小值nums中严格小于instructions[i]的数字数目nums中严格大于instructions[i]的数字数目。要求返回将instructions中所有元素依次插入后的总最小代价结果对10^9 7取余。例如将3插入nums [1,2,3,5]时小于3的有1、22 个大于3的有51 个代价为min(2, 1) 1插入后nums变为[1,2,3,3,5]。示例推演示例 1instructions [1,5,6,2]输出1插入1代价min(0, 0) 0nums [1]插入5代价min(1, 0) 0nums [1,5]插入6代价min(2, 0) 0nums [1,5,6]插入2代价min(1, 2) 1nums [1,2,5,6]总代价0 0 0 1 1示例 2instructions [1,2,3,6,5,4]输出3前四次插入代价均为0插入5时代价为min(3, 1) 1插入4时代价为min(3, 2) 2总代价0 0 0 0 1 2 3示例 3instructions [1,3,3,3,2,4,2,1,2]输出4逐次代价为0, 0, 0, 0, 1, 0, 1, 0, 2总代价4。注意重复元素插入第二个3时严格小于和严格大于3的数量都不包含已存在的3本身这正是严格二字的含义所在。数据范围提示1 instructions.length 10^51 instructions[i] 10^5约束中的10^5量级决定了朴素的双层循环无法通过但同时也提示了值域有限这一关键性质——它直接催生了计数线段树、树状数组这类按值域统计的解法。前置知识本仓库 91 天学算法系列讲义将 二分法 作为独立主题详细讲解其中覆盖了二分查找的问题定义、搜索区间框架[left, right]闭区间写法以及返回最左/最右满足条件的索引等常见变体。本题正是二分变体的实战应用我们需要在有序数组中定位第一个大于等于 x 的位置与第一个大于 x 的位置分别对应bisect_left与bisect_right的语义。此外本题的值域计数需求还可以用线段树或树状数组完成相关模板可参考 OI Wiki 等公开的线段树教程下文会给出完整的计数线段树实现。解法一二分 有序数组模拟插入O(N²)思路二分法的思路非常直接始终维护一个有序的nums每次插入前通过二分查找确定instruction在nums中的位置从而一次算出严格小于与严格大于的数量。Python 标准库bisect提供了两个关键函数bisect.bisect_left(nums, instruction)返回instruction若插入nums时所在的最左索引即第一个 instruction的位置。由于数组有序该索引值l恰好等于严格小于instruction的元素个数。bisect.bisect_right(nums, instruction)返回第一个 instruction的位置。若记r为该索引则len(nums) - r等于大于等于instruction的个数其中包含与instruction相等的元素因此严格大于instruction的个数为len(nums) - r - 1。有了l与r本次插入代价即为min(l, len(nums) - r - 1)累加后对10^9 7取模即可。代码Python3class Solution: def createSortedArray(self, instructions: List[int]) - int: mod 10 ** 9 7 nums [] ans 0 # eg: 1 2 2 3 for instruction in instructions: l bisect.bisect_left(nums, instruction) r bisect.bisect_right(nums, instruction) nums[l:l] [instruction] ans (ans min(l, len(nums) - r - 1)) % mod return ans复杂度分析令 N 为instructions数组长度。时间复杂度遍历instructions需要N次每次二分查找为O(log N)但随后向数组中间插入元素需要移动后续元素单次插入为O(N)因此总时间复杂度为O(N²)。空间复杂度O(N)用于维护有序数组nums。关键细节为什么不能用nums.insert(l, instruction)原文档特别指出若把插入语句写成nums.insert(l, instruction)会超时必须使用切片赋值nums[l:l] [instruction]二者的功能等价都完成在索引l处插入元素但 Python 内部实现存在差异list.insert的实现路径相对较重而切片赋值走的是更高效的底层序列操作具体原因可参考 Stack Overflow 上关于slice assignment faster than list.insert的讨论。在本题10^5级别的数据量下这种常数级别的差异足以决定能否通过。这也提醒我们在使用 Python 刷题时同语义 API 的底层实现差异值得纳入考量。解法二计数线段树O(N log(U))思路二分法虽然思路简单但O(N²)的插入成本是硬伤。由于题目保证1 instructions[i] 10^5值域是有限的于是可以换一个角度不维护元素的有序序列而是维护值域上每个数值出现的次数。为此我们维护一个覆盖[lower, upper]值域的计数线段树它支持两个操作query(l, r)查询[l, r]范围内数值出现的总次数update(x)将数值x的出现次数加 1。于是插入instruction时严格小于instruction的个数 query(1, instruction - 1)严格大于instruction的个数 query(instruction 1, upper)其中upper max(instructions)。代价即为二者的较小值随后调用update(instruction)把当前值记入线段树。核心流程伪代码如下upper max(instructions) # 初始化线段树 seg SegmentTree(upper, 1) for instruction in instructions: # 进行两次查询 l seg.queryCount(1, instruction - 1) r seg.queryCount(instruction 1, upper) ans (ans min(l, r)) % mod # 进行一次更新 seg.updateCount(instruction) return ans线段树将每次查询 更新的开销从O(N)数组移动降到了O(log(upper - lower))从而把总复杂度优化到接近O(N log U)的水平。计数线段树完整代码Python3class SegmentTree: def __init__(self, upper, lower): data:传入的数组 self.lower lower self.upper upper # 申请4倍data长度的空间来存线段树节点 self.tree [0] * (4 * (upper - lower 1)) # 索引i的左孩子索引为2i1右孩子为2i2 # 本质就是一个自底向上的更新过程 # 因此可以使用后序遍历即在函数返回的时候更新父节点。 def update(self, tree_index, l, r, index): tree_index:某个根节点索引 l, r : 此根节点代表区间的左右边界 index : 更新的值的索引 if l index or r index: return self.tree[tree_index] 1 if l r: return mid (l r) // 2 left, right tree_index * 2 1, tree_index * 2 2 self.update(left, l, mid, index) self.update(right, mid 1, r, index) def updateCount(self, index: int): self.update(0, self.lower, self.upper, index) def query(self, tree_index: int, l: int, r: int, ql: int, qr: int) - int: 递归查询区间[ql,..,qr]的值 tree_index : 某个根节点的索引 l, r : 该节点表示的区间的左右边界 ql, qr: 待查询区间的左右边界 if qr l or ql r: return 0 # l 和 r 在 [ql, qr] 内 if ql l and qr r: return self.tree[tree_index] mid (l r) // 2 left, right tree_index * 2 1, tree_index * 2 2 return self.query(left, l, mid, ql, qr) self.query(right, mid 1, r, ql, qr) def queryCount(self, ql: int, qr: int) - int: 返回区间[ql,..,qr]的计数信息 return self.query(0, self.lower, self.upper, ql, qr) class Solution: def createSortedArray(self, instructions: List[int]) - int: mod 10 ** 9 7 ans 0 # eg: 1 2 2 3 upper max(instructions) seg SegmentTree(upper, 1) for instruction in instructions: l seg.queryCount(1, instruction - 1) r seg.queryCount(instruction 1, upper) ans (ans min(l, r)) % mod seg.updateCount(instruction) return ans复杂度分析令 N 为数组长度upper为instructions最大值lower为最小值。由于线段树更新和查询的时间复杂度为O(log(upper - lower))而题目限制1 instructions[i] 10^5因此最坏情况下upper - lower为10^5。线段树使用4 * (upper - lower 1)的空间。时间复杂度O(N log(upper - lower))空间复杂度O(upper - lower)需要说明的是原文档中该解法标注为超时——理论复杂度更优但受限于 Python 递归线段树的常数较大以及题目 10^5 级别的数据规模实际运行可能无法通过全部用例。它更多作为线段树模板的练习与思路展示真正高效的落地实现通常是改用树状数组Fenwick Tree或迭代式线段树把常数压下来。这个对比本身就是一个很好的复杂度理论 vs 工程实现的案例。解法对比与考点总结方案每次插入开销总时间复杂度空间复杂度特点二分 数组插入二分O(log N) 移动O(N)O(N²)O(N)思路直观依赖 Python 切片赋值优化常数计数线段树查询 更新O(log U)O(N log U)O(U)理论更优Python 递归实现常数偏大树状数组拓展思路查询 更新O(log U)O(N log U)O(U)常数小、实现简洁是竞赛与面试的更优落地选择无论采用哪种方案核心考点是一致的将有序数组动态插入问题转化为值域上小于/大于某个数的计数问题再根据值域有限的性质选择合适的数据结构加速。这与仓库中 493. 翻转对Reverse Pairs 的思路同源——那里通过归并排序分治统计逆序数把O(N²)优化到O(N log N)本题则展示了二分模拟与值域计数两条路径。仓库 91 天学算法 的二分法讲义 binary-search.md 覆盖了bisect_left/bisect_right这类边界变体的底层逻辑可作为本题二分细节的延伸阅读。关键点解析严格小于/大于的二分表达bisect_left的返回值即严格小于x的个数len(nums) - bisect_right(x) - 1即严格大于x的个数重复元素不会影响严格比较的计数。Python 插入性能陷阱nums[l:l] [instruction]优于nums.insert(l, instruction)在O(N²)解法中是能否通过的关键常数优化。值域计数思想题目约束1 instructions[i] 10^5是线段树/树状数组解法成立的前提也是这类排名/计数题目的通用突破口。复杂度与常数的权衡线段树理论复杂度更优但语言实现与常数决定了实际表现工程上应结合数据规模选择落地结构。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考