Bagaimanakah anda boleh mencari pendua dalam susunan nombor dari 0 hingga n-1 dalam masa O(n) dan ruang O(1)?

Mencari Pendua dalam O(n) Masa dan O(1) Ruang

Diberi tatasusunan n elemen yang mengandungi nombor dari 0 hingga n -1, di mana beberapa nombor mungkin muncul berbilang kali, matlamatnya adalah untuk mencari elemen pendua dalam masa O(n) dan menggunakan ruang ingatan malar.

Untuk mencapai matlamat ini, kita boleh menggunakan pendekatan menarik yang ' t memerlukan struktur data tambahan seperti jadual cincang.

Algoritma yang dicadangkan beroperasi seperti berikut:

1. Gelung Permutasi:

   • Lelaran melalui tatasusunan untuk i dari 0 hingga n-1.
   • Di dalam gelung ini, lakukan langkah berikut sehingga A[A[i]] bersamaan dengan A[i]. Ini menunjukkan bahawa unsur A[i] berada dalam kedudukannya yang betul.
   • Tukar A[i] dengan A[A[i]]. Ini secara berkesan menggerakkan elemen A[i] selangkah lebih dekat ke kedudukannya yang betul.

2. Gelung Pengenalan Pendua:

   • Lelaran melalui tatasusunan sekali lagi, daripada i daripada 0 kepada n-1.
   • Jika A[i] tidak sama dengan i, ini bermakna terdapat pendua i pada indeks A[i].
   • Cetak A[i] sebagai pendua.

Algoritma ini memastikan semua elemen pendua dikenal pasti. Gelung luar berjalan n kali, manakala gelung dalam berjalan paling banyak n-1 kali. Oleh itu, algoritma berjalan dalam masa O(n). Ia tidak menggunakan sebarang struktur data tambahan, yang bermaksud ia beroperasi dalam ruang O(1).

Kod yang disediakan menunjukkan pelaksanaan algoritma dalam C .

Atas ialah kandungan terperinci Bagaimanakah anda boleh mencari pendua dalam susunan nombor dari 0 hingga n-1 dalam masa O(n) dan ruang O(1)?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!