Design Most Recently Used Queue
要求设计一个队列, 给一个fetch方法, 把输入的第kth元素删除然后放到队列后边.
这个题hints提示了用sqrt桶..就用就行了.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
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); */ |