企业官网建设流程全解析

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

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文基于开源仓库 leetcode（LeetCode 题解集）中 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、2（2 个），大于3的有5（1 个），代价为min(2, 1) = 1，插入后nums变为[1,2,3,3,5]。

示例推演

示例 1：instructions = [1,5,6,2]，输出1

• 插入1，代价min(0, 0) = 0，nums = [1]
• 插入5，代价min(1, 0) = 0，nums = [1,5]
• 插入6，代价min(2, 0) = 0，nums = [1,5,6]
• 插入2，代价min(1, 2) = 1，nums = [1,2,5,6]
• 总代价0 + 0 + 0 + 1 = 1

示例 2：instructions = [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

示例 3：instructions = [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^5
• 1 <= 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取模即可。

代码（Python3）

class 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)的水平。

计数线段树完整代码（Python3）

class SegmentTree: def __init__(self, upper, lower): """ data:传入的数组 """ self.lower = lower self.upper = upper # 申请4倍data长度的空间来存线段树节点 self.tree = [0] * (4 * (upper - lower + 1)) # 索引i的左孩子索引为2i+1，右孩子为2i+2 # 本质就是一个自底向上的更新过程 # 因此可以使用后序遍历，即在函数返回的时候更新父节点。 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 工程实现的案例。

解法对比与考点总结

无论采用哪种方案，核心考点是一致的：将"有序数组动态插入"问题转化为"值域上小于/大于某个数的计数问题"，再根据值域有限的性质选择合适的数据结构加速。这与仓库中 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