HardRating 2208
1649. Create Sorted Array through Instructions
arraybinary-searchdivide-and-conquerbinary-indexed-treesegment-treemerge-sortordered-set
解題說明
Create Sorted Array through Instructions
題目描述: 給定整數陣列 instructions,依次將每個元素插入到一個初始為空的陣列 nums 中。每次插入的代價為 min(嚴格小於該元素的個數, 嚴格大於該元素的個數)。求所有插入的總代價,結果對 10^9 + 7 取餘。
解題思路: 需要一個資料結構能高效地查詢當前陣列中小於 / 大於某值的元素個數。使用 Binary Indexed Tree (BIT / Fenwick Tree),以數值作為索引。插入元素 x 時,小於 x 的個數為 query(x-1),大於 x 的個數為 total - query(x)。取兩者較小值作為代價。
C++ 解法
複雜度分析
時間複雜度:O(n × log M) — 其中 n 為 instructions 長度,M 為元素最大值。每次插入和查詢的 BIT 操作為 O(log M)
空間複雜度:O(M) — BIT 陣列大小為元素最大值
虛擬碼
1. Initialize BIT with size = max value in instructions 2. For each element x in instructions (index i): a. less = BIT.query(x - 1) // count of elements < x b. greater = i - BIT.query(x) // count of elements > x (total - elements <= x) c. cost += min(less, greater) d. BIT.update(x, +1) 3. Return cost mod 10^9+7
其他解法
方法二:線段樹 使用線段樹代替 BIT,支援區間求和和單點更新。時間複雜度相同 O(n log M),但常數較大且實現更複雜。
方法三:合併排序 + 逆序對統計 類似求逆序對的方式,用修改過的合併排序來計算每次插入的代價。時間複雜度 O(n log n),但實現複雜度高。
方法四:平衡 BST(如 Order-Statistics Tree) 使用支援按秩查詢的平衡 BST(如 GNU pb_ds 的 order_of_key)。每次操作 O(log n)。C++ 中可用 __gnu_pbds::tree 實現。
延伸思考
- 如果元素值的範圍很大(例如 10^9),如何用離散化(coordinate compression)來優化 BIT 的空間?
- BIT 和線段樹各有什麼優劣勢?在什麼情境下應該選擇哪一個?
- 如果允許從陣列中間刪除元素,資料結構需要如何擴展?