Bagaimanakah Saya Boleh Mencari Integer Pendua dengan Cekap dalam Tatasusunan Java?

Mencari Pendua dalam Tatasusunan Java

Masalahnya

Anda mempunyai tatasusunan integer dan ingin mengenal pasti mana-mana pendua dengan cekap. Kod awal anda, cuba membandingkan setiap pasangan elemen, gagal mengesan pendua dengan tepat apabila tiada.

Isunya

Kecacatan dalam kod terletak pada pergantungannya pada bendera pendua yang dimulakan kepada palsu dalam semua kes. Jika tiada pendua ditemui, gelung masih akan menetapkan pendua kepada benar apabila menyemak elemen pepenjuru (iaitu, apabila j == k).

Penyelesaian Lebih Nuans

Untuk membetulkan perkara ini, pastikan bahawa bendera pendua ditetapkan kepada benar hanya apabila pendua sebenar ditemui. Ini boleh dicapai dengan mengetepikan perbandingan zipcodeList[j] dengan dirinya sendiri apabila j == k.

Berikut ialah kod yang disemak:

duplicates = false;
for (int j = 0; j < zipcodeList.length; j++) {
    for (int k = 0; k < zipcodeList.length; k++) {
        if (k != j && zipcodeList[k] == zipcodeList[j]) {
            duplicates = true;
        }
    }
}

Pendekatan Lebih Pantas

The penyelesaian di atas mempunyai kerumitan masa jalan O(n²), dengan n ialah bilangan elemen dalam tatasusunan. Untuk tatasusunan besar, pendekatan ini boleh menjadi tidak cekap.

Kaedah yang lebih cekap untuk mengesan pendua ialah memanfaatkan pendekatan berasaskan cincang, mengurangkan kerumitan masa kepada O(n). Berikut ialah contoh menggunakan HashSet:

boolean duplicates(int[] zipcodeList) {
    Set<Integer> lump = new HashSet<>();
    for (int zipcode : zipcodeList) {
        if (lump.contains(zipcode)) {
            return true;
        }
        lump.add(zipcode);
    }
    return false;
}

Sebagai alternatif, penyelesaian O(n) boleh dicapai menggunakan tatasusunan boolean[] (bitmap) untuk menjejaki elemen yang ditemui sebelum ini dan menetapkan pendua kepada benar apabila elemen ditemui kali kedua.

Kesimpulan

Bergantung pada saiz tatasusunan input dan kekerapan daripada pendua, pilihan pendekatan harus disesuaikan untuk mengoptimumkan kecekapan.

Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Mencari Integer Pendua dengan Cekap dalam Tatasusunan Java?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!