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);
 */