1

Java 面接の質問は次のとおりです。

一時バッファを使用せずに、配列から 0 と 1 を分離し、すべての 0 を左側に、1 を右側に配置します。結果を文字列として出力します。たとえば、{0,1,1,0,0,1} を指定すると、出力は "000111" になります。

そして答えは：

public class ZeroOneSeparator {

    public static void zeroOneSeparator(int[] inputArr){

        // for each index, store number of 1's up to the index
        for (int i = 1; i < inputArr.length; i++) {
            inputArr[i] = inputArr[i-1] + inputArr[i];  
        }

        // This is the "magical math" block I don't understand.
        // Why does this "work"?
        for (int i = inputArr.length - 1; i > 0; i--) {
            if (inputArr[i] > 0) {
                inputArr[i-1] = inputArr[i] - 1;
                inputArr[i] = 1;
            } else {
                inputArr[i-1] = 0;
            }
        }

        for (int i = 0; i < inputArr.length; i++) {
            System.out.print(inputArr[i]);
        }
    }

    public static void main(String[] args) {
        int[] inputArr1 = {1,0,1,0,1,1};
        ZeroOneSeparator.zeroOneSeparator(inputArr1);
        System.out.println();
        int[] inputArr2 = {1,1,1,0,0,0,0,0,0,1};
        ZeroOneSeparator.zeroOneSeparator(inputArr2);
        int[] inputArr3 = {}; // intentionally empty
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr3);
        int[] inputArr4 = {0,0,0,0,0,0};
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr4);
        int[] inputArr5 = {0,1,0,1,0,1,0,1};
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr5);
        int[] inputArr6 = {1,1,1,1,1,1,0,0,0,0,0};
        System.out.println();
        ZeroOneSeparator.zeroOneSeparator(inputArr6);
    }
}

このコードをデバッガーでステップ実行しましたが、なぜ機能するのかまだわかりません。誰かが私にそれを説明してもらえますか?

4

3 に答える 3

7

何が起こっているかを見るために例を試してみましょう。次の配列があるとします。

0 1 1 0 1 1 0 0

最初のループ (コメントで指定されているとおり) は、これまでに見られた 1 の総数をカウントアップします。ここで、1 ごとにカウントが増加し、0 ごとに同じままになります。したがって、配列の場合、次のようになります。

0 1 2 2 3 4 4 4

配列の最後の要素が 4 になったことに注意してください。これは 1 の総数です。その事実を次のループで使用します。

最後の要素から開始し、それが 0 より大きいかどうかを確認します。0 より大きい場合は、その要素を 1 に置き換え、そのカウントを 1 減らして前の要素に割り当てます。カウントが 0 になるまで、1 を埋めながらそれを続けます。その時点で、遭遇した各要素を 0 に設定します。

ここで実際に起こっていることは、1 がいくつあるかがわかると、配列の最後から「カウントダウン」して、その数の 1 を埋めることができるということです。その時点で、残りの要素は 0 でなければならないことがわかっているので、その時点で残りの要素を 0 に設定できます。

視覚的には、次のようになります (「現在の要素」が [] で囲まれています)。

0 1 2 2 3 4 4 [4] ->
0 1 2 2 3 4 [3] 1 ->
0 1 2 2 3 [2] 1 1 ->
0 1 2 2 [1] 1 1 1 ->
0 1 2 [0] 1 1 1 1 ->
0 1 [0] 0 1 1 1 1 ->
0 [0] 0 0 1 1 1 1 ->
0 0 0 0 1 1 1 1

このように見ると、「カウントダウン」が非常に明白に見えることに注意してください。

于 2012-07-02T03:50:01.360 に答える
2

配列の最後のインデックスに 1 のカウントがあるため、後ろからループして 1 に置き換えます。コードで行われるトリックは、次のステップで現在の要素が 0 か 1 かを認識できるように、すべてのステップで 1 の数を減らして前の配列要素に格納することです。うまく機能します。すべてが 1 またはほとんどすべてが 1 (配列内の 0 が 1 つだけ) の場合でも、インデックス 0 の要素を変更したときに残った 1 の数がちょうどいい数になるためです。

個人的には、1 の数を記録し、0 の数を導き出し、2 つのループを使用して配列内の数値を出力/設定します。

于 2012-07-02T03:46:17.803 に答える
1

最初の for ループは、各アイテムの左側にある 1 の数をカウントします。入力が の場合、{0,1,1,0,0,1}カウントの結果、入力配列は になり{0,1,2,2,2,3}ます。

最後のインデックス 3 は、リストに 3 つの 1 があることを示しています。2 番目の forループは、リストを逆方向にたどり、最後の 3 つの項目に 1 をマークします。

于 2012-07-02T03:50:38.730 に答える