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

Mencari Pendua dalam O(n) Masa dan O(1) Ruang: Penjelasan Mendalam

Masalah yang ditimbulkan melibatkan mengenal pasti pendua elemen dalam tatasusunan yang mengandungi nombor antara 0 hingga n-1. Cabarannya terletak pada pencapaian ini dengan cekap, dalam kerumitan masa O(n) dan hanya menggunakan ruang ingatan malar (O(1)).

Penyelesaian yang dibentangkan menggunakan teknik bijak yang tidak memerlukan jadual cincang atau data tambahan lain struktur. Sebaliknya, ia memanfaatkan nilai dalam tatasusunan itu sendiri untuk mengenal pasti dan menandai elemen pendua.

1. Mengelaraskan Tatasusunan:

   Gelung dalam mengubah suai tatasusunan berdasarkan logik berikut:

   while A[A[i]] != A[i]
       swap(A[i], A[A[i]])
   end while

   Langkah pilihatur ini memastikan bahawa jika unsur x wujud dalam tatasusunan, sekurang-kurangnya satu kejadiannya akan diletakkan pada A[x]. Ini penting untuk langkah seterusnya.

2. Mengenalpasti Pendua:

   Gelung luar memeriksa setiap elemen A[i]:

   for i := 0 to n - 1
       if A[i] != i then
           print A[i]
       end if
   end for

   Jika A[i] != i, ia menandakan bahawa i tidak hadir di tempat yang sepatutnya dalam tatasusunan. Oleh itu, ia adalah elemen pendua, dan ia dicetak.

3. Analisis Kerumitan Masa:

   Teknik berjalan dalam masa O(n) . Gelung bersarang mempunyai gelung luar yang berulang n kali dan gelung dalam yang melakukan paling banyak n - 1 lelaran (kerana setiap pertukaran membawa satu elemen lebih dekat ke kedudukan yang betul). Oleh itu, jumlah bilangan lelaran dibatasi oleh n*(n - 1), iaitu O(n^2), tetapi boleh dipermudahkan kepada O(n) sebagai n*(n - 1) = n^2 - n = n(n - 1) = n*n - n < n*n = O(n^2) = O(n).

4. Analisis Kerumitan Angkasa:

   Algoritma hanya menggunakan ruang malar , bebas daripada saiz input. Wawasan utama ialah ruang yang digunakan untuk pilih atur sudah ada dalam tatasusunan input. Tiada struktur storan tambahan diperlukan.

5. Nota Tambahan:

   • Algoritma menganggap bahawa tatasusunan mengandungi integer dari 0 hingga n - 1.
   • Kerumitan masa kekal sama, walaupun terdapat pendua.
   • Algoritma ini cekap untuk tatasusunan bersaiz kecil hingga sederhana. Untuk tatasusunan besar, pendekatan alternatif menggunakan struktur data seperti jadual cincang mungkin lebih sesuai.

Atas ialah kandungan terperinci Bagaimanakah kita boleh mencari pendua dalam tatasusunan 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!