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

Mengenal Pendua dalam Tatasusunan Java: A Journey

Di alam Java, tugas penting yang sering dihadapi ialah mencari elemen pendua dalam susunan integer (int []). Walau bagaimanapun, perangkap biasa timbul apabila cuba mengenal pasti pendua ini. Mari terokai isu dan penyelesaiannya.

Pertimbangkan kod berikut:

int[] zipcodelist = // ...

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

Kod ini bertujuan untuk menentukan sama ada senarai kod zip yang diberikan mengandungi sebarang unsur pendua. Walau bagaimanapun, ia gagal mengambil kira senario di mana tiada pendua wujud. Akibatnya, pendua sentiasa berakhir sebagai benar.

Mengenalpasti Kepincangan

Untuk memahami kelemahan, mari kita analisa logiknya. Kod ini mempunyai gelung bersarang yang membandingkan setiap elemen dalam senarai dengan setiap elemen lain. Jika mana-mana dua elemen sepadan, pendua ditetapkan kepada benar, menunjukkan kehadiran pendua. Walau bagaimanapun, apabila tiada pendua, gelung tidak dapat tidak membandingkan elemen dengan dirinya sendiri. Untuk setiap elemen, perbandingan kendiri ini akan menetapkan pendua kepada benar.

Pendekatan Dibetulkan

Untuk memastikan pengesanan pendua yang betul, kod tersebut harus mengecualikan perbandingan diri. Satu cara untuk mencapainya ialah dengan mengubah suai struktur gelung bersarang seperti berikut:

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

Pengubahsuaian ini melangkau perbandingan diri dengan memulakan gelung dalam pada indeks seterusnya (k=j 1).

Meneroka Penyelesaian Alternatif

Sementara pendekatan yang diperbetulkan berfungsi dengan berkesan, terdapat alternatif yang lebih pantas tersedia. Pertimbangkan penyelesaian berasaskan peta cincang berikut:

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

Penyelesaian ini menggunakan set cincang untuk menyemak elemen pendua dengan cekap. Setiap elemen ditambahkan pada set cincang dan jika elemen sudah ada, ia menandakan pendua.

Satu lagi pendekatan cekap melibatkan penggunaan peta bit:

static boolean duplicates(final int[] zipcodelist)
{
   final int MAXZIP = 99999;
   boolean[] bitmap = new boolean[MAXZIP+1];
   java.util.Arrays.fill(bitmap, false);
   for (int item : zipcodelist)
     if (!(bitmap[item] ^= true)) return true;
   }
   return false;
}

Penyelesaian ini mencipta peta bit tatasusunan saiz sama dengan nilai maksimum yang mungkin dalam tatasusunan (MAXZIP). Ia kemudian menggunakan manipulasi bit untuk menetapkan bit yang sepadan untuk setiap elemen yang ditemui dalam tatasusunan input. Jika mana-mana bit sudah ditetapkan, ini menunjukkan pendua.

Hasil Penandaarasan

Untuk menilai prestasi pendekatan ini, kami menjalankan penanda aras dengan saiz senarai yang berbeza-beza. Keputusan menunjukkan bahawa pendekatan bitmap muncul sebagai pemenang yang jelas dari segi kecekapan, terutamanya untuk senarai yang lebih besar:

Array Size	Bitmap (ms)	Hash Set (ms)	Nested Loops (ms)
10	0.0	0.0	0.0
1,000	0.0	0.0	0.0
10,000	0.0	0.0	100.0
100,000	0.0	0.16	9,923.3

Kesimpulan

Mengenal pasti pendua dalam tatasusunan Java boleh menjadi tugas yang mudah setelah perangkapnya difahami. Dengan mengelakkan perbandingan diri atau memanfaatkan pendekatan alternatif seperti set cincang dan peta bit, pengesanan pendua yang cekap dan tepat boleh dicapai, mengoptimumkan prestasi untuk aplikasi Java anda.

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