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 次操作後陣列的狀態(而非總操作數),如何高效查詢?