ゼロ以外の値を右にシフトする : 一般的な配列インタビューの問題-2

導入

この投稿では、配列内のゼロ以外の値をすべて、相対的な順序を維持しながら右にシフトする方法を検討します。この問題は、配列操作とアルゴリズムの最適化についての理解をテストする一般的な面接の質問です。 Java を使用したソリューションを詳しく見てみましょう。

基本的な配列の概念に慣れていない場合は、「Java での配列の基本を理解する: 理解するための簡単なガイド」を参照することをお勧めします。

問題提起

整数の配列が与えられた場合、順序を維持しながらゼロ以外のすべての値を右にシフトしたいと考えます。ゼロ値は左に移動する必要があります。

例:

Input: [1, 2, 0, 3, 0, 0, 4, 0, 2, 9]
Output: [0, 0, 0, 0, 1, 2, 3, 4, 2, 9]

アプローチ

この問題を解決するには、インデックス追跡アプローチを使用します。目標は、配列を右から左に反復処理し、ゼロ以外の要素を正しい位置にシフトすることです。

1. ポインタの初期化: まず、配列の最後のインデックスにポインタを設定します。このポインタは、次のゼロ以外の値を配置する場所をマークします。
2. 配列を移動します: 配列内を右から左に移動します。検出されたゼロ以外の要素ごとに、それをポインタで示された位置に配置し、ポインタをデクリメントします。
3. 残りのゼロ: ゼロ以外の要素がすべて再配置された後、配列の先頭 (つまり、ポインターの左側) の未使用のスポットには自動的にゼロが含まれます。

このアプローチは、時間計算量 O(n) と 空間計算量 O(1) であるため、効率的かつ省スペースになります。

実装

package arrays;

// Time Complexity - O(n)
// Space Complexity - O(1)
public class ShiftNonZeroValuesToRight {

    private void shiftValues(int[] inputArray) {

        /* Variable to keep track of index position to be 
           filled with Non-Zero Value */
        int pointer = inputArray.length - 1;

        // If value is Non-Zero then place it at the pointer index
        for (int i = pointer; i >= 0; i--) {

            /* If there is a non-zero already at correct position,
               just decrement position */
            if (inputArray[i] != 0) {

                if (i != pointer) {
                    inputArray[pointer] = inputArray[i];
                    inputArray[i] = 0;
                }

                pointer--;
            }
        }

        // Printing result using for-each loop
        for (int i : inputArray) {
            System.out.print(i);
        }

        System.out.println();

    }

    public static void main(String[] args) {

        // Test-Case-1 : Ending with a Non-Zero
        int input1[] = { 1, 2, 0, 3, 0, 0, 4, 0, 2, 9 };

        // Test-Case-2 : Ending with Zero
        int input2[] = { 8, 5, 1, 0, 0, 5, 0 };

        // Test-Case-3 : All Zeros
        int input3[] = { 0, 0, 0, 0 };

        // Test-Case-4 : All Non-Zeros
        int input4[] = { 1, 2, 3, 4 };

        // Test-Case-5 : Empty Array
        int input5[] = {};

        // Test-Case-6 : Empty Array
        int input6[] = new int[5];

        // Test-Case-7 : Uninitialized Array
        int input7[];

        ShiftNonZeroValuesToRight classObject = new ShiftNonZeroValuesToRight();
        classObject.shiftValues(input1); // Result : 0000123429
        classObject.shiftValues(input2); // Result : 0008515
        classObject.shiftValues(input3); // Result : 0000
        classObject.shiftValues(input4); // Result : 1234
        classObject.shiftValues(input5); // Result :
        classObject.shiftValues(input6); // Result : 00000
        classObject.shiftValues(input7); // Result : Compilation Error - Array may not have been initialized

    }
}

コードの説明

1. shiftValues メソッド:
   • 入力パラメータ: inputArray – 処理する必要がある配列。
   • ポインタの初期化: ポインタは配列の最後のインデックスに初期化されます。
   • 配列トラバーサル: ループは配列の末尾から先頭に向かって繰り返し、ゼロ以外の要素をチェックします。ゼロ以外の要素はポインタが示す位置に移動し、ポインタはデクリメントされます。
   • 結果: ゼロ以外の要素をすべて移動すると、追加の手順を行わなくても、配列内の残りの要素は自然にゼロになります。
2. メインメソッド:
   • main メソッドには、非ゼロまたはゼロ値で終わる配列、すべてゼロまたはすべて非ゼロの配列、空の配列、初期化されていない配列など、さまざまなシナリオを実証するためのさまざまなテスト ケースが含まれています。

エッジケースの考慮

• 空の配列: プログラムは例外をスローせずに空の配列を処理します。

• 初期化されていない配列: 初期化されていない配列のテスト ケースのコメントを解除するとコンパイル エラーが発生し、配列の初期化の重要性がわかります。

結論

このプログラムは、配列内のゼロ以外の値を右にシフトする効率的な方法を提供します。これは、注意深くポインタを管理することで、時間と空間の両方の複雑さの観点から最適なソリューションを導き出すことができることを示す良い例です。

配列に関する別のよくある面接の質問については、私の以前の投稿「非ゼロ値を左にシフト: よくある配列面接の問題-1」を参照してください。

ご質問やご提案がございましたら、お気軽に以下にコメントを残してください。コーディングを楽しんでください!

以上がゼロ以外の値を右にシフトする : 一般的な配列インタビューの問題-2の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。