java - 如何让我的函数在恒定时间内运行？

Question

我刚收到我的作业，我失去了一个功能的分数，因为它不是在恒定时间运行，它不够高效。我将不得不经历预约和等待从我的教授那里得到答复的麻烦，我想知道这里是否有人现在可以帮助我。

我有一个函数可以从 ArrayList 中删除并随机返回一个项目。

public T pick() {
    int end = l.size() - 5;
    if (l.size() == 0)
        return null;
    assert(next >= 2 && next <= l.size()-1);
    T x = l.remove(next);
    next = (l.size() > 0) ? r.nextInt(l.size()) : -5;
    return x;
}

有人可以指出我可以做些什么来提高这段代码的效率吗？先感谢您！

Answer 1

该方法ArrayList.remove具有线性时间复杂度，如果next未接近结束。诀窍是将 next 位置的元素与最后一个元素交换，并删除最后一个元素。

T x = l.get(next);
l.set(next, l.get(l.size() - 1));
l.remove(l.size() - 1);