Werte ungleich Null nach links verschieben: Ein häufiges Array-Interview-Problem-1

Einführung

In technischen Interviews treten häufig Probleme bei der Array-Manipulation auf. In diesem Beitrag befassen wir uns mit einem häufigen Problem: Werte ungleich Null nach links verschieben und dabei die Reihenfolge der Elemente ungleich Null beibehalten und alle Nullen nach rechts verschieben.

Wenn Sie mit den grundlegenden Array-Konzepten nicht vertraut sind, empfehle ich Ihnen, sich „Understanding Array Basics in Java: A Simple Guide“ anzuschauen, um sich auf den neuesten Stand zu bringen!

Problemstellung

Bei einem Array von Ganzzahlen besteht Ihre Aufgabe darin, alle Nicht-Null-Elemente auf die linke Seite zu verschieben und gleichzeitig alle Null-Elemente nach rechts zu verschieben. Die relative Reihenfolge der Nicht-Null-Elemente muss beibehalten werden.

Beispiel:

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

Ansatz

Wir können dieses Problem in O(n) Zeit mit einem einzigen Durchgang durch das Array lösen, und die Lösung wird eine Raumkomplexität von O(1) haben.

1. Verwenden Sie einen Zeiger, um den Index für das nächste Element ungleich Null zu verfolgen.
2. Durchlaufen Sie das Array und platzieren Sie Elemente ungleich Null am Index des Zeigers.
3. Erhöhen Sie den Zeiger jedes Mal, wenn ein Element ungleich Null platziert wird.

Der Kodex

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
    }

}

Erläuterung

• Die Methode shiftValues iteriert durch das Eingabearray.

• Wenn ein Wert ungleich Null gefunden wird, wird er am aktuellen Zeigerindex platziert und das Element am aktuellen Index wird durch 0 ersetzt.

• Der Zeiger wird dann inkrementiert, um die nächste Position für ein Element ungleich Null zu verfolgen.

• Wenn an der richtigen Position (d. h. am Zeigerindex) bereits ein Wert ungleich Null vorhanden ist, erhöht die Methode einfach den Zeiger, ohne einen Austausch vorzunehmen.

• Dies wird fortgesetzt, bis das gesamte Array verarbeitet ist.

Zeit- und Raumkomplexität

• Zeitkomplexität: O(n), wobei n die Länge des Arrays ist.

• Raumkomplexität: O(1), da wir das Array an Ort und Stelle ändern.

Randfälle

• Alle Nullen: Wenn das Array nur Nullen enthält, bleibt es unverändert.

• Keine Nullen: Wenn keine Nullen vorhanden sind, bleibt die ursprüngliche Reihenfolge der Elemente erhalten.

• Leeres Array: Die Funktion sollte leere Arrays ohne Probleme verarbeiten.

Abschluss

Dieses Problem zeigt, wie wichtig es ist, Array-Manipulationstechniken und ihre Effizienz bei der Codierung von Interviews zu verstehen. Das Beherrschen solcher Probleme kann Ihre Fähigkeiten zur Problemlösung erheblich verbessern!

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