Design Most Recently Used Queue
要求设计一个队列, 给一个fetch方法, 把输入的第kth元素删除然后放到队列后边.
这个题hints提示了用sqrt桶..就用就行了.
class MRUQueue {
List<Integer>[] q;
int len;
public MRUQueue(int n) {
len = (int)Math.sqrt(n) + 1;
q = new LinkedList[len];
for(int i = 0 ; i < len; i++) {
q[i] = new LinkedList<Integer>();
}
for(int i = 1 ; i <= n; i++) {
q[(i - 1) / len].add(i);
}
}
public int fetch(int k) {
k--; // change the index to start with 0
int j = k % len;
int res = q[k / len].remove(j);
q[len - 1].add(res);
for(int i = k / len; i < len - 1; i++) {
q[i].add(q[i+1].remove(0));
}
return res;
}
}
/**
* Your MRUQueue object will be instantiated and called as such:
* MRUQueue obj = new MRUQueue(n);
* int param_1 = obj.fetch(k);
*/