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

導入

技術面接では、配列操作の問題が頻繁に起こります。この投稿では、一般的な問題、つまりゼロ以外の要素の順序を維持しながら、ゼロ以外の値を左にシフトし、すべてのゼロを右に移動するという問題に取り組みます。

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

問題提起

整数の配列が与えられた場合、あなたのタスクは、すべてのゼロ要素を右側に押しながら、すべての非ゼロ要素を左側に移動することです。ゼロ以外の要素の相対的な順序は保持される必要があります。

例:

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

アプローチ

配列を 1 回通過することで、この問題を O(n) 時間で解くことができ、その解の空間複雑さは O(1) になります。

1. ポインターを使用して、次のゼロ以外の要素のインデックスを追跡します。
2. 配列を反復処理し、ポインターのインデックスにゼロ以外の要素を配置します。
3. ゼロ以外の要素が配置されるたびにポインターをインクリメントします。

コード

package arrays;

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

    private void shiftValues(int[] inputArray) {

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

        // If value is Non-Zero then place it at the pointer index
        for (int i = 0; i < inputArray.length; i++) {

            /* If there is a non-zero already at correct position, 
                     just increment 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 : Starting with a Non-Zero
        int input1[] = { 1, 2, 0, 3, 0, 0, 4, 3, 2, 9 };

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

        // 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[];

        ShiftNonZeroValuesToLeft classObject = new ShiftNonZeroValuesToLeft();
        classObject.shiftValues(input1); // Result : 1234329000
        classObject.shiftValues(input2); // Result : 5129000
        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
    }

}

説明

• shiftValues メソッドは入力配列を反復処理します。

• ゼロ以外の値が見つかった場合、その値は現在のポインター インデックスに配置され、現在のインデックスにある要素は 0 に置き換えられます。

• その後、ポインタがインクリメントされて、非ゼロ要素の次の位置を追跡します。

• 正しい位置 (つまり、ポインターのインデックス) に既にゼロ以外の値がある場合、メソッドはスワップを行わずに単にポインターをインクリメントします。

• これは配列全体が処理されるまで続きます。

時間と空間の複雑さ

• 時間計算量: O(n)、n は配列の長さです。

• 空間複雑度: O(1)、配列を適切に変更しているためです。

エッジケース

• すべてゼロ: 配列にすべてゼロが含まれている場合、配列は変更されません。

• ゼロなし: ゼロがない場合、要素の元の順序が保持されます。

• 空の配列: この関数は空の配列を問題なく処理する必要があります。

結論

この問題は、インタビューのコーディングにおける配列操作テクニックとその効率を理解することの重要性を示しています。このような問題をマスターすると、問題解決スキルが大幅に向上します!

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