> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1649.create-sorted-array-through-instructions.md). # 1649. 通过指令创建有序数组 ## 题目描述 ``` 给你一个整数数组 instructions ，你需要根据 instructions 中的元素创建一个有序数组。一开始你有一个空的数组 nums ，你需要 从左到右 遍历 instructions 中的元素，将它们依次插入 nums 数组中。每一次插入操作的 代价 是以下两者的 较小值 ： nums 中 严格小于  instructions[i] 的数字数目。 nums 中 严格大于  instructions[i] 的数字数目。 比方说，如果要将 3 插入到 nums = [1,2,3,5] ，那么插入操作的 代价 为 min(2, 1) (元素 1 和  2 小于 3 ，元素 5 大于 3 ），插入后 nums 变成 [1,2,3,3,5] 。 请你返回将 instructions 中所有元素依次插入 nums 后的 总最小代价 。由于答案会很大，请将它对 109 + 7 取余 后返回。   示例 1： 输入：instructions = [1,5,6,2] 输出：1 解释：一开始 nums = [] 。 插入 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 解释：一开始 nums = [] 。 插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。 插入 2 ，代价为 min(1, 0) = 0 ，现在 nums = [1,2] 。 插入 3 ，代价为 min(2, 0) = 0 ，现在 nums = [1,2,3] 。 插入 6 ，代价为 min(3, 0) = 0 ，现在 nums = [1,2,3,6] 。 插入 5 ，代价为 min(3, 1) = 1 ，现在 nums = [1,2,3,5,6] 。 插入 4 ，代价为 min(3, 2) = 2 ，现在 nums = [1,2,3,4,5,6] 。 总代价为 0 + 0 + 0 + 0 + 1 + 2 = 3 。 示例 3： 输入：instructions = [1,3,3,3,2,4,2,1,2] 输出：4 解释：一开始 nums = [] 。 插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。 插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3] 。 插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3] 。 插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3,3] 。 插入 2 ，代价为 min(1, 3) = 1 ，现在 nums = [1,2,3,3,3] 。 插入 4 ，代价为 min(5, 0) = 0 ，现在 nums = [1,2,3,3,3,4] 。 ​​​​​插入 2 ，代价为 min(1, 4) = 1 ，现在 nums = [1,2,2,3,3,3,4] 。 插入 1 ，代价为 min(0, 6) = 0 ，现在 nums = [1,1,2,2,3,3,3,4] 。 插入 2 ，代价为 min(2, 4) = 2 ，现在 nums = [1,1,2,2,2,3,3,3,4] 。 总代价为 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4 。   提示： 1 <= instructions.length <= 105 1 <= instructions[i] <= 105 ``` ## 前置知识 * [二分法](/leetcode-solution/91/binary-search.md) * [线段树](https://oi-wiki.org/ds/seg/) ## 公司 * 暂无 ## 二分法 ### 思路 二分法的思路比较简单，直接模拟插入即可。每次只需要保证插入之后还是有序的，这样就可以通过二分查找，计算出**严格大于** 和 **严格小于** x 的数目了。 * 使用 `bisect.bisect_left(nums, instruction)` 可以计算出 instruction 如果插入到 nums ，instruction 在 nums 中的索引是。 * 使用 `bisect.bisect_right(nums, instruction)` 和 bisect\_left 类似，只不过对于 nums 已经存在 instruction 了， bisect\_left 会尝试插入到其左侧，bisect\_right 则会尝试插入到其右侧。 根据 bisect\_left 和 bisect\_right，我们就可计算出 **严格大于** 和 **严格小于** instruction 的数目了。接下来，我们只需要模拟插入即可。 ### 代码 代码支持：Python3 Python3 Code: ```py 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 需要 $N$ 次，每次都需要插入数据， 由于插入数组的时间复杂度是 $O(N)$。 因此总的时间复杂度为 $O(N^2)$ * 空间复杂度：$O(N)$ 需要注意的是，如下代码会超时： ```py nums.insert(l, instruction) ``` 也就是说必须使用切片语法才可以： ```py nums[l:l] = [instruction] ``` 具体原因大家可以参考这个 [stackoverflow 的回答](https://stackoverflow.com/questions/12537716/why-is-slice-assignment-faster-than-list-insert) ## 线段树（超时） ### 思路 这里我直接使用了**计数线段树的模板**。不懂线段树的可以先看下 [线段树教程](https://oi-wiki.org/ds/seg/) 我们可以维护一个 \[lower,upper] 的一个线段树。线段树支持的操作： * query(l, r): 查询 \[l, r] 范围内的数的个数 * update(x): 将 x 更新到线段树 ![](https://p.ipic.vip/zogfe5.jpg) 因此我们的目标其实就是 min(query(1, instruction - 1), query(instruction + 1, upper))，其中 upper 为 instructions 的最大树。 核心代码： ```py 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 ``` ### 代码 代码支持：Python3 Python3 Code: ```py 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 为数组长度。 由于线段树更新和查询的时间复杂度为 $O(log(upper - lower))$，其中 upper 为 instructions 最大值，lower 为 instructions 最小值。由于题目限制了 $1 <= instructions\[i] <= 10^5$，因此最坏情况下 upper - lower 为 10 ^5。 线段树使用了 $4 \* (upper - lower + 1)$ 的空间。 * 时间复杂度：$O(Nlog(upper-lower))$ * 空间复杂度：$O(upper- lower)$