HardRating 2282
2659. Make Array Empty
arraybinary-searchgreedybinary-indexed-treesegment-treesortingordered-set
解題說明
Make Array Empty
題目描述： 給定一個包含不同整數的陣列 nums，重複以下操作直到陣列為空：如果第一個元素是陣列中的最小值，則移除它；否則將第一個元素移到陣列末尾。返回使陣列為空所需的總操作次數。
解題思路： 觀察：元素被移除的順序就是元素值的排序順序（從小到大）。關鍵是計算移除每個元素時需要多少次「旋轉」操作。
將元素按值排序，記錄每個元素的原始索引。移除第 i 個元素（排序後第 i 小）時，需要從上一個被移除的位置「旋轉」到當前位置，途中跳過已被移除的元素。
可以用 BIT（樹狀陣列）維護剩餘元素的位置，快速計算兩個位置之間有多少個未移除的元素。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 排序 O(n log n)，每次 BIT 操作 O(log n)，共 n 次
空間複雜度：O(n) — BIT 和排序輔助陣列
虛擬碼
1. Initialize BIT with all positions marked as present 2. Sort elements by value, recording original indices 3. Set prev = 0 (starting position) 4. For each element in sorted order (smallest to largest): a. cur = original index of current element b. If cur >= prev: operations += count of remaining elements in [prev, cur] c. Else (wrap around): operations += remaining in [prev, n-1] + remaining in [0, cur] d. Remove cur from BIT e. Set prev = cur 5. Return total operations
其他解法
-
線段樹法：使用線段樹代替 BIT 維護區間和。功能更強大（可以支援區間更新），但本題只需單點更新和區間查詢，BIT 更簡潔。
-
有序集合法：使用
std::set或policy-based tree維護剩餘元素的索引。每次用order_of_key計算排名差。時間複雜度相同 O(n log n)。
延伸思考
- 如果陣列中有重複元素（移除值最小的那一個，若有多個取最左邊的），如何修改？
- 如果操作改為「移除最大值」而非最小值，需要調整什麼？
- 如果要找出第 k 次操作後陣列的狀態（而非總操作數），如何高效查詢？