Mengalihkan Nilai Bukan Sifar Ke Kanan : Masalah Temu Bual Tatasusunan Biasa-2

pengenalan

Dalam siaran ini, kami akan meneroka cara mengalihkan semua nilai bukan sifar dalam tatasusunan ke kanan sambil mengekalkan susunan relatifnya. Masalah ini ialah soalan temu bual biasa yang menguji pemahaman anda tentang manipulasi tatasusunan dan pengoptimuman algoritma. Mari kita mendalami penyelesaian menggunakan Java.

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, kami mahu mengalihkan semua nilai bukan sifar ke kanan sambil mengekalkan susunannya. Nilai sifar hendaklah dialihkan ke kiri.

Contoh:

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

Pendekatan

Kami akan menggunakan pendekatan penjejakan indeks untuk menyelesaikan masalah ini. Matlamatnya adalah untuk mengulangi tatasusunan dari kanan ke kiri dan mengalihkan unsur bukan sifar ke kedudukan yang betul.

1. Mulakan Penunjuk: Mulakan dengan menetapkan penunjuk pada indeks terakhir tatasusunan. Penunjuk ini akan menandakan di mana nilai bukan sifar seterusnya harus diletakkan.
2. Melintasi Tatasusunan: Bergerak melalui tatasusunan dari kanan ke kiri. Untuk setiap elemen bukan sifar yang ditemui, letakkannya pada kedudukan yang ditunjukkan oleh penunjuk dan kurangkan penunjuk.
3. Baki Sifar: Selepas semua elemen bukan sifar diletakkan semula, sebarang titik yang tidak digunakan pada permulaan tatasusunan (iaitu, di sebelah kiri penuding) akan mengandungi sifar secara automatik.

Pendekatan ini mempunyai kerumitan masa O(n) dan kerumitan ruang O(1), menjadikannya cekap dan menjimatkan ruang.

Perlaksanaan

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

    }
}

Penjelasan Kod

1. Kaedah ShiftValues:
   • Parameter Input: inputArray – Tatasusunan yang perlu diproses.
   • Permulaan Penunjuk: penuding dimulakan ke indeks terakhir tatasusunan.
   • Traversal Tatasusunan: Gelung berulang dari penghujung tatasusunan ke arah permulaan, menyemak elemen bukan sifar. Unsur bukan sifar dialihkan ke kedudukan yang ditunjukkan oleh penuding dan penunjuk dikurangkan.
   • Keputusan: Setelah semua elemen bukan sifar dialihkan, elemen yang tinggal dalam tatasusunan secara semula jadi akan menjadi sifar tanpa sebarang langkah tambahan.
2. Kaedah Utama:
   • Kaedah utama mengandungi pelbagai kes ujian untuk menunjukkan senario yang berbeza, seperti tatasusunan yang berakhir dengan nilai bukan sifar atau sifar, tatasusunan dengan semua sifar atau semua bukan sifar, tatasusunan kosong dan tatasusunan yang tidak dimulakan.

Kes Edge Dipertimbangkan

• Tatasusunan Kosong: Program ini mengendalikan tatasusunan kosong tanpa membuang pengecualian.

• Tasusunan Tidak Dimulakan: Menyahkomen kes ujian untuk tatasusunan yang tidak dimulakan akan mengakibatkan ralat penyusunan, menunjukkan kepentingan pemulaan tatasusunan.

Kesimpulan

Program ini menyediakan cara yang cekap untuk mengalihkan nilai bukan sifar ke kanan dalam tatasusunan. Ia adalah contoh yang bagus tentang bagaimana pengurusan penunjuk yang berhati-hati boleh membawa kepada penyelesaian yang optimum dari segi kerumitan masa dan ruang.

Untuk satu lagi soalan temu bual biasa mengenai tatasusunan, lihat siaran saya sebelum ini tentang Mengalihkan Nilai Bukan Sifar ke Kiri: Masalah Temuduga Tatasusunan Biasa-1

Jika anda mempunyai sebarang soalan atau cadangan, sila tinggalkan komen di bawah. Selamat mengekod!

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