Bagaimanakah Saya Boleh Mengeluarkan Pendua dengan Cekap daripada Tatasusunan Tanpa Menggunakan Set?

Penyingkiran Penduaan Tatasusunan yang Cekap Tanpa Set

Dalam beberapa cabaran pengaturcaraan, anda mungkin perlu mengalih keluar nilai pendua daripada tatasusunan tanpa menggunakan pra-bina struktur data seperti Set atau HashSet. Berikut ialah pendekatan yang dioptimumkan yang boleh anda pertimbangkan:

Pelaksanaan anda yang disediakan melakukan berbilang hantaran ke atas tatasusunan, yang membawa kepada kerumitan masa yang tidak cekap. Untuk memperbaikinya, pertimbangkan untuk menggunakan gabungan dua pengoptimuman:

1. Gunakan Tatasusunan Penanda:

Buat tatasusunan penanda bersaiz sama dengan elemen maksimum dalam tatasusunan asal. Mulakan semua elemen kepada 0. Apabila anda menemui elemen dalam tatasusunan asal, tetapkan kedudukan yang sepadan dalam tatasusunan penanda kepada 1. Dengan cara ini, anda hanya perlu menyemak tatasusunan penanda untuk menentukan sama ada elemen itu adalah pendua atau tidak.

2. Gunakan Penunjuk Indeks Akhir:

Kekalkan penunjuk indeks akhir yang menunjukkan indeks yang mana tatasusunan tanpa pendua telah dikira. Apabila anda menemui pendua, alihkan elemen selepas pendua ke kiri, kurangkan indeks akhir dengan sewajarnya.

Berikut ialah versi kod anda yang dioptimumkan menggunakan pengoptimuman ini:

public static int[] removeDuplicates(int[] arr) {
    // Initialize the marker array with zeros
    int[] marker = new int[1000000];
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        // Check if the element is already marked as duplicate
        if (marker[arr[i]] == 1) {
            // If it's a duplicate, shift the elements after it to the left
            for (int j = i + 1; j < end; j++, i++) {
                arr[i] = arr[j];
            }
            end--;
            i--;
        } else {
            // If it's not a duplicate, mark it in the marker array
            marker[arr[i]] = 1;
        }
    }

    return arr;
}

Pelaksanaan ini meningkatkan prestasi dengan ketara dengan mengelakkan hantaran berbilang ke atas tatasusunan dan mengurangkan bilangan pertukaran elemen yang diperlukan.

Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Mengeluarkan Pendua dengan Cekap daripada Tatasusunan Tanpa Menggunakan Set?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!