侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【模拟】设计最近使用(MRU)队列

GabrielxD
2022-06-14 / 0 评论 / 0 点赞 / 29 阅读 / 500 字 / 正在检测是否收录...

题目

1756. 设计最近使用(MRU)队列


设计一种类似队列的数据结构,该数据结构将最近使用的元素移到队列尾部。

实现 MRUQueue 类:

  • MRUQueue(int n) 使用 n 个元素: [1,2,3,...,n] 构造 MRUQueue
  • 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 <= n <= 2000
  • 1 <= k <= n
  • 最多调用 2000fetch

进阶:找到每次 fetch 的复杂度为 O(n) 的算法比较简单。你可以找到每次 fetch 的复杂度更佳的算法吗?

解题

方法一:模拟

思路

根据题意用数组或者集合模拟即可。

集合模拟:

class MRUQueue {
    private List<Integer> list;

    public MRUQueue(int n) {
        list = new ArrayList<Integer>(n) {{
            for (int i = 1; i <= n ; i++) this.add(i);
        }};
    }
    
    public int fetch(int k) {
        int ele = list.remove(k - 1);
        list.add(ele);
        return ele;
    }
}

使用数组模拟:

class MRUQueue {
    private int[] arr;

    public MRUQueue(int n) {
        arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = i + 1;
    }
    
    public int fetch(int k) {
        int n = arr.length;
        if (k == n) return arr[n - 1];
        int ele = arr[k - 1];
        System.arraycopy(arr, k, arr, k - 1, n - k);
        arr[n - 1] = ele;
        return ele;
    }
}
0

评论区