当前位置：首页 > 力扣 > 力扣1649题解：利用树状数组与离散化创建有序数组

力扣1649题解：利用树状数组与离散化创建有序数组

6个月前 (09-11)

一、题目解读

力扣1649题要求计算将无序数组转化为有序数组所需的最小代价，每次插入元素的代价为两侧比它大或小的元素数量中的较小值。题目核心在于高效统计元素插入前后的相对位置关系，需要设计一种支持动态更新与区间查询的数据结构。

二、解题思路

采用离散化 + 树状数组（Fenwick Tree）的解决方案。首先通过离散化将原数组映射到索引范围[1, n]，消除数值差异带来的计算复杂度。随后利用树状数组维护有序序列的统计信息：通过查询前缀和快速获取小于/等于目标值的元素数量，进而推导出插入代价。该思路巧妙将数值比较转化为索引操作，大幅降低时间复杂度。

三、解题步骤

1. 离散化处理：对原数组排序并去重，生成有序列表sorted，每个元素num通过lower_bound映射为排名rank（即离散化索引）。

2. 初始化树状数组：基于sorted长度构建FenwickTree，用于维护累计计数。

3. 循环处理每个元素：

○ 查询小于当前值的元素数量less = ft.query(rank-1)，小于等于的数量lessEqual = ft.query(rank)。

○ 计算当前元素的出现次数same = lessEqual - less，大于当前值的数量greater = 总数 - lessEqual。

○ 代价取两侧较小值：min(less, greater)，累加总代价并取模防溢出。

○ 更新树状数组：ft.update(rank, 1)记录当前元素插入。

4. 返回总代价：最终累加值即为最小插入代价。

四、代码与注释

class FenwickTree {
private:
    vector<int> tree;
public:
    FenwickTree(int size) : tree(size + 1) {} // 构造树状数组（多1位防止索引越界）
    
    void update(int index, int delta) {
        while (index < tree.size()) { // 从index开始向上更新区间和
            tree[index] += delta;
            index += index & -index; // 二进制最低位+1跳跃
        }
    }
    
    int query(int index) {
        int sum = 0;
        while (index > 0) { // 从index开始向下累加前缀和
            sum += tree[index];
            index -= index & -index; // 二进制最低位清零跳跃
        }
        return sum;
    }
};

class Solution {
public:
    int createSortedArray(vector<int>& instructions) {
        const int MOD = 1e9 + 7; // 防止整数溢出
        // 离散化：排序去重生成有序映射列表
        vector<int> sorted = instructions;
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        
        FenwickTree ft(sorted.size());
        int totalCost = 0;
        
        for (int num : instructions) {
            // 获取离散化后的排名（索引+1，因树状数组从1开始）
            int rank = lower_bound(sorted.begin(), sorted.end(), num) - sorted.begin() + 1;
            // 统计小于当前值的元素数
            int less = ft.query(rank - 1);
            // 统计小于等于当前值的元素数
            int lessEqual = ft.query(rank);
            // 当前元素出现次数
            int same = lessEqual - less;
            // 大于当前值的元素数
            int greater = ft.query(sorted.size()) - lessEqual;
            
            // 代价取两侧较小值，累加并取模
            int cost = min(less, greater);
            totalCost = (totalCost + cost) % MOD;
            
            // 更新树状数组计数
            ft.update(rank, 1);
        }
        
        return totalCost;
    }
};