Werte ungleich Null nach rechts verschieben: Ein häufiges Array-Interview-Problem-2

Einführung

In diesem Beitrag erfahren Sie, wie Sie alle Werte ungleich Null in einem Array nach rechts verschieben und dabei ihre relative Reihenfolge beibehalten. Bei diesem Problem handelt es sich um eine häufig gestellte Frage in Vorstellungsgesprächen, die Ihr Verständnis von Array-Manipulation und Algorithmusoptimierung auf die Probe stellt. Lassen Sie uns mit Java in die Lösung eintauchen.

Wenn Sie mit grundlegenden Array-Konzepten nicht vertraut sind, empfehle ich Ihnen, sich „Array-Grundlagen in Java verstehen: Eine einfache Anleitung“ anzusehen, um sich auf den neuesten Stand zu bringen!

Problemstellung

Angesichts eines Arrays von ganzen Zahlen möchten wir alle Werte ungleich Null nach rechts verschieben und dabei ihre Reihenfolge beibehalten. Die Nullwerte sollten nach links verschoben werden.

Beispiel:

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

Ansatz

Wir werden einen Index-Tracking-Ansatz verwenden, um dieses Problem zu lösen. Das Ziel besteht darin, das Array von rechts nach links zu durchlaufen und Nicht-Null-Elemente an ihre richtigen Positionen zu verschieben.

1. Initialisieren Sie einen Zeiger: Beginnen Sie damit, einen Zeiger auf den letzten Index des Arrays zu setzen. Dieser Zeiger markiert, wo der nächste Wert ungleich Null platziert werden soll.
2. Durchqueren Sie das Array:Bewegen Sie sich von rechts nach links durch das Array. Platzieren Sie jedes angetroffene Nicht-Null-Element an der durch den Zeiger angegebenen Position und dekrementieren Sie den Zeiger.
3. Verbleibende Nullen: Nachdem alle Nicht-Null-Elemente neu positioniert wurden, enthalten alle nicht verwendeten Stellen am Anfang des Arrays (d. h. links vom Zeiger) automatisch Nullen.

Dieser Ansatz hat eine zeitliche Komplexität von O(n) und eine räumliche Komplexität von O(1), was ihn sowohl effizient als auch platzsparend macht.

Durchführung

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

    }
}

Erläuterung des Kodex

1. shiftValues-Methode:
   • Eingabeparameter: inputArray – Das Array, das verarbeitet werden muss.
   • Zeigerinitialisierung:Zeiger wird auf den letzten Index des Arrays initialisiert.
   • Array-Traversal: Die Schleife iteriert vom Ende des Arrays zum Anfang und sucht nach Elementen ungleich Null. Elemente ungleich Null werden an die durch den Zeiger angegebene Position verschoben und der Zeiger wird dekrementiert.
   • Ergebnis: Sobald alle Nicht-Null-Elemente verschoben wurden, sind die verbleibenden Elemente im Array ohne zusätzliche Schritte natürlich Nullen.
2. Hauptmethode:
   • Die Hauptmethode enthält verschiedene Testfälle, um verschiedene Szenarien zu demonstrieren, z. B. Arrays, die mit einem Wert ungleich Null oder Null enden, Arrays mit ausschließlich Nullen oder ausschließlich Nicht-Nullen, leere Arrays und nicht initialisierte Arrays.

Randfälle berücksichtigt

• Leere Arrays: Das Programm verarbeitet leere Arrays, ohne eine Ausnahme auszulösen.

• Nicht initialisierte Arrays: Das Auskommentieren des Testfalls für nicht initialisierte Arrays führt zu einem Kompilierungsfehler, was die Bedeutung der Array-Initialisierung zeigt.

Abschluss

Dieses Programm bietet eine effiziente Möglichkeit, Werte ungleich Null in einem Array nach rechts zu verschieben. Es ist ein großartiges Beispiel dafür, wie eine sorgfältige Zeigerverwaltung zu optimalen Lösungen hinsichtlich der zeitlichen und räumlichen Komplexität führen kann.

Eine weitere häufige Interviewfrage zu Arrays finden Sie in meinem vorherigen Beitrag zum Thema „Verschiebung von Nicht-Null-Werten nach links: Ein häufiges Array-Interviewproblem-1“

Wenn Sie Fragen oder Anregungen haben, können Sie unten gerne einen Kommentar hinterlassen. Viel Spaß beim Codieren!

Das obige ist der detaillierte Inhalt vonWerte ungleich Null nach rechts verschieben: Ein häufiges Array-Interview-Problem-2. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!