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

Mengalih Keluar Pendua daripada Tatasusunan Dengan Cekap Tanpa Perlu Menetapkan

Anda telah berusaha untuk mencipta penyelesaian tersuai untuk menghapuskan elemen pendua daripada tatasusunan, tetapi kesesakan prestasi telah muncul. Untuk mengoptimumkan pelaksanaan ini, kami akan menganalisis kelemahan pendekatan anda dan mencadangkan strategi alternatif.

Analisis Algoritma Anda

Algoritma anda cuba mencari pendua dengan membandingkan setiap elemen dengan setiap elemen berikutnya. Perbandingan menyeluruh ini menghasilkan kerumitan masa O(n^2). Untuk tatasusunan yang besar, strategi ini boleh menjadi sangat tidak cekap.

Pendekatan Dioptimumkan

Untuk meningkatkan prestasi dengan ketara, kami boleh mempertimbangkan pengoptimuman berikut:

1. Menggunakan Peta Cincang: Laksanakan peta cincang untuk menyimpan elemen unik ditemui semasa lelaran. Memandangkan setiap elemen ditambahkan pada tatasusunan, semak sama ada ia sudah wujud sebagai kunci dalam peta cincang. Jika tidak, tambahkannya. Pendekatan ini membolehkan operasi carian masa malar yang cekap, mengurangkan kerumitan masa kepada O(n).
2. Isih Sebelum Penapisan: Isih tatasusunan dalam tertib menaik. Kini, elemen pendua akan bersebelahan antara satu sama lain. Lelaran melalui tatasusunan yang diisih dan hapuskan pendua bersebelahan, menghasilkan algoritma O(n) masa linear.

Penyelesaian Alternatif

Sementara pengoptimuman yang disebutkan di atas boleh meningkatkan prestasi algoritma anda, anda juga boleh mempertimbangkan yang lain yang telah ditetapkan teknik:

• Tetapkan Koleksi: Memandangkan anda perlu mengelak daripada menggunakan Set, kami tidak akan menyelidiki pilihan ini.
• Menggunakan Koleksi Isih : Sama seperti mengisih sebelum menapis, manfaatkan koleksi yang diisih seperti TreeSet atau NavigableSet. Ia secara automatik mengekalkan susunan yang disusun dan membenarkan pengambilan elemen yang cekap, menghasilkan kerumitan O(n log n).

Pelaksanaan

Berdasarkan pendekatan yang dioptimumkan, versi diubah suai algoritma anda menggunakan peta cincang boleh jadi:

public static int[] removeDuplicatesWithoutSet(int[] arr) {

    HashMap<Integer, Boolean> map = new HashMap<>();
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        if (map.containsKey(arr[i])) {
            int shiftLeft = i;
            for (int k = i + 1; k < end; k++, shiftLeft++) {
                arr[shiftLeft] = arr[k];
            }
            end--;
            i--;
        } else {
            map.put(arr[i], true);
        }
    }

    int[] whitelist = new int[end];
    for (int i = 0; i < end; i++) {
        whitelist[i] = arr[i];
    }
    return whitelist;
}

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!