1

課題が返ってきたばかりで、一定の時間に実行されず、十分に効率的ではなかったため、1 つの関数の評価を失いました。予約を取り、教授からの返事を待つという面倒なことをしなければなりませんでした。

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;
}

このコードをより効率的にするために何ができるかを誰かが指摘できますか? 前もって感謝します！

4

1 に答える 1

3

メソッドは、終わりに近づいていないArrayList.remove場合、線形時間の複雑さを持ちます。トリックnextは、次の位置にある要素を最後の要素と交換し、最後の要素を削除することです。

T x = l.get(next);
l.set(next, l.get(l.size() - 1));
l.remove(l.size() - 1);
于 2013-10-15T03:47:52.110 に答える