2

少し前のプログラミングクラスでは、比較的単純なタスクが与えられました。その本質は次のように要約できます。

nが常に <= mであるn文字列の配列 (リストではない) を格納し、新しい文字列を追加して古い文字列を削除できるようにします。(この例では、mは 50 でした)

その後、このことについて友達と話し合ったとき、私たち 3 人全員が別の方法で解決したことに気付きました。私の質問 (単なる好奇心から) は、私たちのどちらが最良の答え (すべてが等しい場合) とその理由です。

友人 Aは、本質的に ArrayList を実装することにしました。異なるサイズの新しい配列を作成し、元の配列のすべての要素をforループで新しい配列に入れます（追加/削除していたものをプラスまたはマイナスします）。

友人 Bは単純に長さmの配列を作成し、値を null に設定して要素を削除し (例: array[13] = null)、空のスポットが見つかるまでインデックス 0 から順方向にスクラブして要素を追加しました (これはforループでした)。

Friend C [Me]も長さmforの配列を作成しましたが、文字列が削除されたときに、n -1 が常に最後の値のインデックスになるように、後続のすべての値を前方にシフトしました (つまり、ループでインデックスを 1 減らしました)。 n > 0)、nは新しい値を追加するインデックスでもありました (for文字列を追加するためのループを排除します)。

それはかなり基本的なクラスであり、私たちが行った限り、彼らは私たちがどのようにそれを行ったかを気にしませんが、私たちは興味があります.

編集：重要かもしれない何かを省略したことに気づきました。この問題は、インデックスではなく値(例: ) で文字列を削除することを指定していたため、値 (およびそのインデックス) を見つけることも必要でした。removeString("someString")

4

2 に答える 2

1

私にとって、あなたのバージョンはすべての効果的です。でループをなくすだけですSystem.arraycopy。理由は、追加する配列ごとに for ループがあるためです。B には 2 つの for ループがあり、あなたには 1 つしかありません。

あなたのバージョンのサンプル プログラムを で作成しましたSystem.arraycopyが、それが最も効率的な方法だと思います。

import java.util.Arrays;

public class Sample {

private int currentIndex = 0;
private String[] strings = null;

public Sample(int length) {
    strings = new String[length];
}

public Sample(String[] strs) {
    if(strs == null)
        throw new NullPointerException();
    strings = strs;
}

public boolean add(String str) {
    if (currentIndex == strings.length)
        return false;
    strings[currentIndex++] = str;
    return true;

}

public boolean remove(int index) {
    if (index >= strings.length)
        return false;
    System.arraycopy(strings, index + 1, strings, index, (strings.length
            - index - 1));
    strings[--currentIndex] = null;
    return true;
}

public boolean remove(String value) {
    if (value == null || value.isEmpty()) {
        return false;// we are saved since value is null or empty;)
    }
    for (int count = 0; count < strings.length; count++) {
        if (value.equals(strings[count])) {
            remove(count);
            break;
        }
    }
    return true;
}

/**
 * @param args
 */
public static void main(String[] args) {
    Sample sample = new Sample(5);
    sample.add("a");
    sample.add("b");
    sample.add("c");
    sample.add("d");
    sample.add("e");
    sample.remove("a");

    System.out.println(Arrays.toString(sample.strings));

}

}
于 2012-09-30T06:34:57.377 に答える
0

作成した配列は最終的にシステムに実装されるため、正解はない可能性があります。したがって、システム要件に依存します。しかし、一般的に効率を考慮すると：

  • 友人Aの解決策は、私には厄介なようです。要素を追加/削除するために新しい配列を作成すると、メモリと CPU サイクルが無駄になります。また、それは ArrayList が Java で実装されている方法ではないと思います。

  • 友人 B のソリューションは、最悪の場合の時間の複雑さは友人 C のものと同じですが、はるかに優れたパフォーマンスを発揮する可能性があります。文字列の順序は重要ではないため、これが最適です。

  • Friend C のソリューションも、実際には非常に効率的です。要素の追加に関しては、すでにインデックス ien があるため、パフォーマンスも良好です。

ただし、前に述べたように、実際には実装しているシステムに依存します。しかし、まとめとして、A < B = C と言う必要があります。

ディグビジェイ

于 2012-09-30T05:50:29.097 に答える