MediumRating 1335

1409. Queries on a Permutation With Key

arraybinary-indexed-treesimulation

解題說明

Queries on a Permutation With Key

題目描述：給定 queries 陣列和整數 m。初始有一個排列 P = [1, 2, ..., m]。對於每個查詢 queries[i]，找到 queries[i] 在 P 中的位置（從 0 開始），記錄該位置，然後將 queries[i] 移到 P 的最前面。回傳每次查詢的位置結果。

解題思路：直接模擬即可。由於 m 和 queries 長度最大為 1000，暴力模擬的效率已足夠。對於每個查詢，在排列中找到目標元素的位置，記錄後將其移到最前面。

C++ 解法

複雜度分析

時間複雜度：O(n × m) — 其中 n 為 queries 長度，每次查詢需要 O(m) 時間搜尋和移動

空間複雜度：O(m) — 儲存排列 P

虛擬碼

1. Initialize permutation P = [1, 2, ..., m]
2. For each query q in queries:
   a. Find position of q in P
   b. Record position in result
   c. Remove q from its position and insert at front of P
3. Return result

其他解法

方法二：Binary Indexed Tree (BIT) 將排列擴展為長度 n + m 的陣列，查詢的元素放在前 n 個位置。用 BIT 維護前綴和來快速查詢位置。每次查詢和移動操作的時間降為 O(log(n+m))，總時間 O(n log(n+m))。

方法三：平衡 BST / Order-Statistics Tree 使用支援按秩查詢的平衡 BST。每個元素以其「優先級」為 key，移到前面時更新優先級為最小值。每次操作 O(log m)。

延伸思考

如果 m 非常大（例如 10^6），直接模擬會超時，你會使用什麼資料結構來優化？
如果查詢不是移到最前面，而是移到最後面，結果會如何改變？
這個問題與 LRU Cache 有什麼相似之處？能否借鑑 LRU Cache 的設計？

Queries on a Permutation With Key — CaffeCode