# 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 ``` ## 前置知识 * [二分法](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/91/binary-search) * [线段树](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)$ --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1649.create-sorted-array-through-instructions.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.