Formatted question description: https://leetcode.ca/all/1756.html
1756. Design Most Recently Used Queue
Level
Medium
Description
Design a queue-like data structure that moves the most recently used element to the end of the queue.
Implement the MRUQueue
class:
MRUQueue(int n)
constructs theMRUQueue
withn
elements:[1,2,3,...,n]
.fetch(int k)
moves thek-th
element (1-indexed) to the end of the queue and returns it.
Example 1:
Input:
["MRUQueue", "fetch", "fetch", "fetch", "fetch"]
[[8], [3], [5], [2], [8]]
Output:
[null, 3, 6, 2, 2]
Explanation:
MRUQueue mRUQueue = new MRUQueue(8); // Initializes the queue to [1,2,3,4,5,6,7,8].
mRUQueue.fetch(3); // Moves the 3rd element (3) to the end of the queue to become [1,2,4,5,6,7,8,3] and returns it.
mRUQueue.fetch(5); // Moves the 5th element (6) to the end of the queue to become [1,2,4,5,7,8,3,6] and returns it.
mRUQueue.fetch(2); // Moves the 2nd element (2) to the end of the queue to become [1,4,5,7,8,3,6,2] and returns it.
mRUQueue.fetch(8); // The 8th element (2) is already at the end of the queue so just return it.
Constraints:
1 <= n <= 2000
1 <= k <= n
- At most
2000
calls will be made tofetch
.
Follow up: Finding an O(n)
algorithm per fetch
is a bit easy. Can you find an algorithm with a better complexity for each fetch
call?
Solution
Use an array to represent the queue.
In the constructor, initialize the array with length n
and elements from 1 to n
.
In method fetch
, fetch the element at the given index, move the elements after the element to the previous indices, put the element at the last index, and return the element.
Follow up
- better than o(N) fetch, first thought is binary search.
- but worst case it could be still o(N), on average it will be better than flat o(N)
Java
class MRUQueue {
int size;
int[] queue;
public MRUQueue(int n) {
size = n;
queue = new int[n];
for (int i = 0; i < n; i++)
queue[i] = i + 1;
}
public int fetch(int k) {
int num = queue[k - 1];
for (int i = k; i < size; i++)
queue[i - 1] = queue[i];
queue[size - 1] = num;
return num;
}
}
/**
* Your MRUQueue object will be instantiated and called as such:
* MRUQueue obj = new MRUQueue(n);
* int param_1 = obj.fetch(k);
*/