Hard

题目描述

给你一个整数数组 instructions，你需要根据 instructions 中的元素创建一个有序数组。一开始你有一个空的数组 nums，对于 instructions 中的每个元素，从左到右将其插入到 nums 数组中。每次插入操作的代价是以下两者的最小值：

  1. nums 中严格小于 instructions[i] 的数字数目
  2. 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^9 + 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

示例 3：

输入：instructions = [1,3,3,3,2,4,2,1,2]
输出：4

提示：

  • 1 <= instructions.length <= 10^5
  • 1 <= instructions[i] <= 10^5

解题思路

这个问题的核心在于高效地查询和维护有序数组中元素的排名信息。

思路分析：

对于每次插入操作，我们需要知道：

  1. 有多少个元素严格小于当前插入值
  2. 有多少个元素严格大于当前插入值

朴素的做法是维护一个有序数组，每次插入时用二分查找找到位置，但这样会超时。

优化方案 - 树状数组/二元索引树：

由于数值范围有限（1 ≤ instructions[i] ≤ 10^5），我们可以用树状数组来维护每个数值的出现次数。

对于插入值 val：

  • 小于 val 的元素个数 = query(val-1)
  • 大于 val 的元素个数 = total - query(val) （其中 total 是当前已插入的元素总数）

树状数组支持 O(log n) 的单点更新和前缀和查询，非常适合这个问题。

算法步骤：

  1. 初始化树状数组，支持 10^5 的数值范围
  2. 对于每个待插入的数值 val：
    • 计算小于 val 的元素个数
    • 计算大于 val 的元素个数
    • 代价为两者的最小值
    • 在树状数组中增加 val 的计数
  3. 累加所有代价并返回结果

代码实现

class Solution {
public:
    int createSortedArray(vector<int>& instructions) {
        const int MOD = 1e9 + 7;
        const int MAX_VAL = 1e5;
        
        // 树状数组
        vector<int> bit(MAX_VAL + 1, 0);
        
        auto update = [&](int idx, int val) {
            for (; idx <= MAX_VAL; idx += idx & -idx) {
                bit[idx] += val;
            }
        };
        
        auto query = [&](int idx) {
            int sum = 0;
            for (; idx > 0; idx -= idx & -idx) {
                sum += bit[idx];
            }
            return sum;
        };
        
        long long cost = 0;
        for (int i = 0; i < instructions.size(); i++) {
            int val = instructions[i];
            int smaller = query(val - 1);  // 严格小于val的个数
            int larger = i - query(val);    // 严格大于val的个数
            cost = (cost + min(smaller, larger)) % MOD;
            update(val, 1);
        }
        
        return cost;
    }
};

class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        MOD = 10**9 + 7
        MAX_VAL = 10**5
        
        # 树状数组
        bit = [0] * (MAX_VAL + 1)
        
        def update(idx, val):
            while idx <= MAX_VAL:
                bit[idx] += val
                idx += idx & -idx
        
        def query(idx):
            total = 0
            while idx > 0:
                total += bit[idx]
                idx -= idx & -idx
            return total
        
        cost = 0
        for i, val in enumerate(instructions):
            smaller = query(val - 1)  # 严格小于val的个数
            larger = i - query(val)    # 严格大于val的个数
            cost = (cost + min(smaller, larger)) % MOD
            update(val, 1)
        
        return cost

public class Solution {
    public int CreateSortedArray(int[] instructions) {
        const int MOD = 1000000007;
        const int MAX_VAL = 100000;
        
        // 树状数组
        int[] bit = new int[MAX_VAL + 1];
        
        void Update(int idx, int val) {
            for (; idx <= MAX_VAL; idx += idx & -idx) {
                bit[idx] += val;
            }
        }
        
        int Query(int idx) {
            int sum = 0;
            for (; idx > 0; idx -= idx & -idx) {
                sum += bit[idx];
            }
            return sum;
        }
        
        long cost = 0;
        for (int i = 0; i < instructions.Length; i++) {
            int val = instructions[i];
            int smaller = Query(val - 1);  // 严格小于val的个数
            int larger = i - Query(val);    // 严格大于val的个数
            cost = (cost + Math.Min(smaller, larger)) % MOD;
            Update(val, 1);
        }
        
        return (int)cost;
    }
}

var createSortedArray = function(instructions) {
    const MOD = 1e9 + 7;
    const MAX_VAL = 1e5;
    
    // 树状数组
    const bit = new Array(MAX_VAL + 1).fill(0);
    
    const update = (idx, val) => {
        for (; idx <= MAX_VAL; idx += idx & -idx) {
            bit[idx] += val;
        }
    };
    
    const query = (idx) => {
        let sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += bit[idx];
        }
        return sum;
    };
    
    let cost = 0;
    for (let i = 0; i < instructions.length; i++) {
        const val = instructions[i];
        const smaller = query(val - 1);  // 严格小于val的个数
        const larger = i - query(val);    // 严格大于val的个数
        cost = (cost + Math.min(smaller, larger)) % MOD;
        update(val, 1);
    }
    
    return cost;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log m)，其中 n 是指令数组长度，m 是数值范围（10^5）。每次操作在树状数组上需要 O(log m) 时间
空间复杂度O(m)，需要大小为 m 的树状数组空间

相关题目