Mengalihkan Nilai Bukan Sifar Ke Kiri: Masalah Temu Bual Tatasusunan Biasa-1

pengenalan

Dalam temu bual teknikal, masalah manipulasi tatasusunan sering dihadapi. Dalam siaran ini, kami akan menangani masalah biasa: Menukar nilai bukan sifar ke kiri sambil mengekalkan susunan unsur bukan sifar dan menolak semua sifar ke kanan.

Jika anda tidak biasa dengan konsep tatasusunan asas, saya syorkan anda menyemak Memahami Asas Tatasusunan dalam Java: Panduan Mudah untuk meningkatkan kelajuan!

Pernyataan Masalah

Memandangkan tatasusunan integer, tugas anda ialah mengalihkan semua elemen bukan sifar ke sebelah kiri sambil menolak semua unsur sifar ke kanan. Susunan relatif unsur bukan sifar mesti dikekalkan.

Contoh:

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

Pendekatan

Kita boleh menyelesaikan masalah ini dalam O(n) masa menggunakan satu laluan melalui tatasusunan, dan penyelesaiannya akan mempunyai kerumitan ruang O(1).

1. Gunakan penuding untuk menjejaki indeks bagi elemen bukan sifar seterusnya.
2. Lelar melalui tatasusunan, meletakkan elemen bukan sifar pada indeks penuding.
3. Naikkan penunjuk setiap kali elemen bukan sifar diletakkan.

Kod

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
    }

}

Penjelasan

• Kaedah shiftValues berulang melalui tatasusunan input.

• Jika nilai bukan sifar ditemui, ia diletakkan pada indeks penunjuk semasa dan elemen pada indeks semasa digantikan dengan 0.

• Penunjuk kemudiannya dinaikkan untuk menjejaki kedudukan seterusnya bagi elemen bukan sifar.

• Jika sudah ada nilai bukan sifar pada kedudukan yang betul (iaitu, pada indeks penunjuk), kaedah hanya menambah penunjuk tanpa membuat sebarang pertukaran.

• Ini berterusan sehingga keseluruhan tatasusunan diproses.

Kerumitan Masa & Ruang

• Kerumitan Masa: O(n), dengan n ialah panjang tatasusunan.

• Kerumitan Ruang: O(1), memandangkan kami sedang mengubah suai tatasusunan di tempatnya.

Kes Tepi

• Semua Sifar: Jika tatasusunan mengandungi semua sifar, ia akan kekal tidak berubah.

• Tiada Sifar: Jika tiada sifar, susunan unsur asal dikekalkan.

• Susun Kosong: Fungsi harus mengendalikan tatasusunan kosong tanpa masalah.

Kesimpulan

Masalah ini mempamerkan kepentingan memahami teknik manipulasi tatasusunan dan kecekapannya dalam temu bual pengekodan. Menguasai masalah sebegini boleh meningkatkan kemahiran menyelesaikan masalah anda!

Atas ialah kandungan terperinci Mengalihkan Nilai Bukan Sifar Ke Kiri: Masalah Temu Bual Tatasusunan Biasa-1. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!