通过指令创建有序数组

难度: Hard

给你一个整数数组 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 后的 总最小代价 。由于答案会很大，请将它对 10⁹ + 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 <= 10⁵
1 <= instructions[i] <= 10⁵

Submission

运行时间: 1058 ms

内存: 27.9 MB

class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        MOD = 10**9+7
        # cnts = Counter(instructions)
        # idxes = {num:i+1 for i, num in enumerate(sorted(cnts.keys()))}
        # n = len(cnts)
        mx = max(instructions)
        arr = [0] * (mx+1)

        def update(i):
            while i<=mx:
                arr[i] += 1
                i += i & (-i)
            
        def query(i):
            res = 0
            while i>0:
                res += arr[i]
                i &= i - 1
            return res 

        cnts_ = [0]*(mx+1)
        ans = 0
        for i, instruction in enumerate(instructions):
            # idx = idxes[instruction]
            mn = query(instruction)
            ans = (ans + min(i-mn, mn - cnts_[instruction])) % MOD
            update(instruction)
            cnts_[instruction] += 1

        return ans % MOD

Explain

该题解使用了树状数组 (Binary Indexed Tree, BIT) 来高效维护和查询插入数字的位置信息。BIT 通过部分累加实现对前缀和的快速查询和单点的更新，使得我们可以迅速计算出在当前数字之前和之后的数字数量。每次插入时，计算小于当前数字的数量和大于当前数字的数量，然后取较小值为插入的代价，累加至总代价中。此外，使用了一个数组来计数每个数字的出现次数，用于帮助计算大于当前数字的数量。

时间复杂度: O(n logM)

空间复杂度: O(M)

class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        MOD = 10**9+7  # 使用大数模防止整数溢出
        mx = max(instructions)  # 找到最大值以确定BIT的大小
        arr = [0] * (mx+1)  # 初始化树状数组

        def update(i):  # 树状数组的更新函数
            while i<=mx:
                arr[i] += 1  # 在相应位置增加计数
                i += i & (-i)  # 移动到下一个位置
            
        def query(i):  # 树状数组的查询函数
            res = 0
            while i>0:
                res += arr[i]  # 累加到当前位置的计数
                i &= i - 1  # 移动到前一个位置
            return res 

        cnts_ = [0]*(mx+1)  # 计数数组，记录每个数字的出现次数
        ans = 0
        for i, instruction in enumerate(instructions):
            mn = query(instruction)  # 查询当前数字之前的计数
            ans = (ans + min(i-mn, mn - cnts_[instruction])) % MOD  # 计算最小代价并累加
            update(instruction)  # 更新树状数组
            cnts_[instruction] += 1  # 更新计数数组

        return ans % MOD  # 返回结果，并进行取模操作

Explore

树状数组（BIT）相较于AVL树或红黑树等平衡二叉搜索树，具有更简单的实现和较低的常数因子。例如，在BIT中，更新和查询操作都可以以O(log n)的时间复杂度进行，但实现方式比较直观简单。此外，BIT在处理前缀和及其变种问题时相对高效，尤其适合于频繁进行修改和查询操作的场景。而AVL树和红黑树虽然也支持O(log n)时间内的动态插入、删除和查询操作，但实现更为复杂，且在处理前缀和问题时不如BIT直接高效。考虑到本题中需要高效计算插入数字的位置信息的代价，BIT因其简洁有效而被选用。

树状数组在此题中用于快速计算任意数字之前已插入的元素数量，即实现快速查询前缀和。更新操作确保每次插入数字时，树状数组可以反映出所有小于等于当前数字的元素的累计数量。而计数数组（cnts_）则用于记录每个数字具体出现的次数。这是因为，虽然树状数组能快速查找小于等于某数的元素总数，但无法直接得知某一具体数字出现的次数。在计算插入代价时，需要知道当前数字已出现的次数，以计算大于该数字的元素数量，这就需要用到计数数组。因此，两个数组各司其职，共同完成代价的计算和更新。

在本题中，插入代价是指插入一个数字时导致数组失序的最小可能改动。这里的表达式`min(i-mn, mn - cnts_[instruction])`计算的是插入数字`instruction`时的最小代价。其中，`i`代表当前处理到的数字的索引（从0开始），`mn`是通过树状数组查询得到的，表示小于等于`instruction`的数字数量，`cnts_[instruction]`表示数字`instruction`之前出现的次数。具体来说，`i-mn`计算的是大于`instruction`的元素数量（即总数减去小于等于`instruction`的数量），而`mn - cnts_[instruction]`计算的是小于`instruction`的元素数量（即小于等于`instruction`的数量减去`instruction`自身的出现次数）。计算这两个值的最小值可以得到插入`instruction`的最小代价，即最少需要移动的元素数量来保持数组有序。