題目資訊

• 題目編號: 1756
• 題目連結: Design Most Recently Used Queue
• 主題: Array, Hash Table, Stack, Design, Binary Indexed Tree, Ordered Set

題目敘述

設計一個類似佇列的資料結構，它會將最近使用的元素移動到佇列的末尾。

實作 MRUQueue 類：

• MRUQueue(int n) 建立一個含有 $n$ 個元素的 MRUQueue：$[1,2,3,\ldots,n]$。
• int fetch(int k) 將第 $k$ 個元素（以 1 開頭編號）移動到佇列的末尾並返回它。

範例 1

輸入：

["MRUQueue", "fetch", "fetch", "fetch", "fetch"]
[[8], [3], [5], [2], [8]]

輸出：

[null, 3, 6, 2, 2]

解釋：

MRUQueue mRUQueue = new MRUQueue(8); // 初始化佇列為 [1,2,3,4,5,6,7,8]。
mRUQueue.fetch(3); // 將第 3 個元素 (3) 移動到佇列末尾變成 [1,2,4,5,6,7,8,3]，並返回它。
mRUQueue.fetch(5); // 將第 5 個元素 (6) 移動到佇列末尾變成 [1,2,4,5,7,8,3,6]，並返回它。
mRUQueue.fetch(2); // 將第 2 個元素 (2) 移動到佇列末尾變成 [1,4,5,7,8,3,6,2]，並返回它。
mRUQueue.fetch(8); // 第 8 個元素 (2) 已經在佇列的末尾，所以直接返回它。

限制條件：

• $1 \leq n \leq 2000$
• $1 \leq k \leq n$
• 最多呼叫 2000 次 fetch。

進階:

找到一個每次 fetch 呼叫的 $O(n)$ 演算法有點容易。你能找到一個對每次 fetch 呼叫有更好複雜度的演算法嗎？

直覺

此問題要求設計一個類似隊列的數據結構，使其可以根據使用情況存取和重新排列其元素。主要操作涉及將指定元素移動到隊列末尾，標記為最近使用。該結構模仿了一個常見的現實場景，即經常存取的項目被保持在容易存取的位置。

解法

此解法使用了 C++ 中的一個簡單但有效的數據結構——向量（vector）來實現MRU（Most Recently Used）隊列。以下是逐步解決方法：

1. 初始化：

   • 構造函數初始化一個向量以模擬隊列，將其填充從 1 到 $n$ 的整數。這表示 MRUQueue 的初始狀態，所有元素按順序排列。

2. 提取操作：

   • fetch 方法旨在通過存取第 $k$ 個元素並將其移動到隊列末尾來操作隊列，並返回其值。
   • 演算法如下：
     • 存取第 $(k-1)$ 個位置的元素（由於 C++ 中使用 0 基索引）並將它附加到向量末尾。這標記該元素為最近使用。
     • 然後從向量中移除原始第 $k$ 個元素，以保持一致性並避免數據結構中的重複。
     • 最後，該方法返回被移動到末尾的元素值，可以通過向量的 back 方法直接存取。

通過利用向量的動態數組特性——高效的存取和修改——該解法實現了所需的操作。fetch 操作的複雜度受到移除元素時需要移動其他元素的主導，因此在最壞情況下是 $O(n)$；然而，給定問題的約束，這仍然是可以接受的。

程式碼

C++

class MRUQueue {
public:
    // 向量用於儲存MRUQueue的元素
    vector<int> queue;

    // 构造函数，初始化队列的元素从1到n
    MRUQueue(int n) {
        for (int i = 1; i <= n; i++) {
            queue.emplace_back(i);
        }
    }

    // 取得第k个元素（以1为索引），将其移到队列的末尾，并返回它
    int fetch(int k) {
        // 将第k个元素添加到队列的末尾
        queue.push_back(queue[k - 1]);
        // 从其位置移除原本的第k个元素
        queue.erase(queue.begin() + k - 1);
        // 返回最近移动的元素
        return queue.back();
    }
};

/**
 * 您的MRUQueue对象将被实例化并按如下方式调用：
 * MRUQueue* obj = new MRUQueue(n);
 * int param_1 = obj->fetch(k);
 */

Python

class MRUQueue:
    # 用於儲存MRUQueue元素的列表
    queue = []

    # 構造函數，用元素從1到n初始化隊列
    def __init__(self, n):
        for i in range(1, n + 1):
            self.queue.append(i)

    # 獲取第k個元素（以1為索引），將其移動到隊列末尾並返回它
    def fetch(self, k):
        # 將第k個元素添加到隊列末尾
        self.queue.append(self.queue[k - 1])
        # 從其位置移除原始第k個元素
        self.queue.pop(k - 1)
        # 返回最近移動的元素
        return self.queue[-1]

# 您的MRUQueue對象將被實例化並如此調用:
# obj = MRUQueue(n)
# param_1 = obj.fetch(k)

複雜度分析

• 時間複雜度: fetch 操作的時間複雜度是 $O(n)$。這是因為 fetch 函數涉及在向量的末尾插入元素以及在中間移除元素。從向量的開頭或中間移除元素需要移動後續元素，在最壞情況下，需要 $O(n)$ 的時間，其中 $n$ 是向量中當前元素的數量。
• 空間複雜度: 空間複雜度是 $O(n)$。MRUQueue 所使用的空間與隊列中元素的數量成正比，這些元素被初始化為 $n$ 個，其中 $n$ 是允許的最大大小（根據限制最多為 2000）。