Bagaimana untuk Mencari Pendua dalam Tatasusunan dengan O(n) Masa dan O(1) Ruang?

Algoritma Cekap untuk Mencari Pendua dalam O(n) Masa dan O(1) Ruang

Dalam cabaran pengaturcaraan ini, kami mencari yang cekap algoritma untuk mengenal pasti dan mencetak elemen pendua dalam tatasusunan integer antara 0 hingga n-1, dengan kemungkinan pengulangan. Cabaran itu memerlukan algoritma yang beroperasi dalam kerumitan masa O(n) dan hanya menggunakan ruang ingatan malar.

Satu pendekatan berkesan untuk masalah ini ialah teknik "pengubahsuaian tatasusunan". Algoritma berfungsi seperti berikut:

1. Gelung Pertama:

   • Mulakan gelung yang berulang pada setiap elemen dalam tatasusunan, dilambangkan sebagai A[i].
   • Untuk setiap A[i], tentukan sama ada A[A[i]] bersamaan dengan A[i].
   • Jika tidak, tukar A[i] dengan A[ A[i]].

2. Gelung Kedua:

   • Tetapkan semula gelung untuk berulang pada setiap A[i] sekali lagi.
   • Untuk mana-mana A[i] yang tidak sama dengan i, cetak A[i]. Langkah ini mengenal pasti elemen pendua kerana mana-mana elemen bukan pendua akan mempunyai A[A[i]] sama dengan i (iaitu, ia berada dalam kedudukan yang betul).

Algoritma ini beroperasi dalam masa O(n) kerana setiap elemen disemak dan diubah suai paling banyak sekali dalam gelung pertama. Selain itu, memandangkan tiada struktur data tambahan digunakan, ia hanya menggunakan ruang O(1).

Sebagai contoh, pertimbangkan tatasusunan input {1, 2, 3, 1, 3, 0, 6}. Selepas menjalankan algoritma, tatasusunan diubah suai seperti berikut:

[1, 2, 3, 1, 3, 0, 0]

Gelung kedua kemudian mencetak elemen pendua, 1 dan 3.

Atas ialah kandungan terperinci Bagaimana untuk Mencari Pendua dalam Tatasusunan dengan O(n) Masa dan O(1) Ruang?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!