难度: Medium
Submission
运行时间: 93 ms
内存: 17.1 MB
class MRUQueue:
def __init__(self, n: int):
self.q = [*range(1, n + 1)]
def fetch(self, k: int) -> int:
self.q.append(self.q.pop(k - 1))
return self.q[-1]
# Your MRUQueue object will be instantiated and called as such:
# obj = MRUQueue(n)
# param_1 = obj.fetch(k)
Explain
该题解实现了一个最近使用（MRU）队列的类，其中包含一个初始化方法和一个取数方法。在初始化方法中，队列以整数顺序从1到n进行填充。在取数方法中，给定一个索引k，该方法将选定位置的元素移至队列的最末端，并返回该元素的值。这种方法确保了最近被访问的元素总是被移到队列的末尾，符合MRU（最近最常用）的缓存策略。
时间复杂度: O(n)
空间复杂度: O(n)
# 类定义
class MRUQueue:
# 初始化函数，创建一个从1到n的整数列表
def __init__(self, n: int):
self.q = [*range(1, n + 1)]
# fetch函数，根据传入的索引k，返回并更新最近使用的元素
def fetch(self, k: int) -> int:
# 将索引k-1的元素移动到列表末尾
self.q.append(self.q.pop(k - 1))
# 返回移动后位于列表末尾的元素
return self.q[-1]
# 实例化和调用示例
# obj = MRUQueue(n)
# param_1 = obj.fetch(k)
Explore
在实现MRU队列时选择使用列表而不是链表，主要是因为列表在Python中的实现（例如数组）可以提供更快的随机访问性能。这意味着可以直接通过索引访问元素，这在MRU队列的实现中是必需的，因为需要根据传入的索引k来访问特定元素。虽然链表在删除和添加操作中的时间复杂度是O(1)，列表的删除和添加操作（尤其是在列表末尾）也非常高效，特别是使用pop和append方法时。此外，Python的列表内部优化使得其在实际应用中的性能往往优于预期。
是的，在fetch方法中如果k值超出当前队列的长度，将会引发索引错误，因为列表索引将超出范围。为了增强代码的健壯性，可以在fetch方法中添加检查来确保k值在有效范围内。例如，可以在方法开始时添加一个条件语句检查k的值是否在1到列表长度的范围内。如果k值不在这个范围内，可以抛出一个异常或者返回一个错误信息，这样可以有效防止程序因索引错误而崩溃。
MRU（最近最常用）队列有多种实际应用场景，特别是在需要根据最近使用模式优化数据访问或资源分配的情况下。例如，在缓存系统中，MRU策略可以用来决定哪些数据应该保留在缓存中。当系统需要频繁访问最近使用的数据时，MRU队列可以确保这些数据快速可用。此外，MRU策略也可以在页面置换算法中使用，例如在操作系统的内存管理中，最近经常访问的页面更可能在近期内再次被访问，因此可以保留在内存中，以减少页面错误率。