Bagaimana Mencari Pendua dalam Tatasusunan dengan Kerumitan Masa dan Ruang Optimum?

Mencari Pendua dengan Kerumitan Masa dan Ruang Optimum

Pengenalan:
Tugas mengesan unsur pendua dalam tatasusunan adalah masalah lazim dalam pengaturcaraan. Walaupun penyelesaian menggunakan struktur data tambahan seperti jadual cincang menawarkan kesederhanaan, ia menjejaskan kecekapan ruang. Artikel ini membentangkan algoritma bijak yang mengenal pasti pendua dalam masa linear, O(n), sambil mengekalkan penggunaan ruang yang berterusan, O(1).

Pernyataan Masalah:
Diberikan tatasusunan daripada n elemen antara 0 hingga n-1, di mana beberapa nombor mungkin muncul beberapa kali, cari elemen pendua dalam tatasusunan.

Algoritma Optimum:

// Iterate through the array
for i = 0 to n - 1:
    // Swap elements until A[A[i]] = A[i]
    while A[A[i]] != A[i]:
        swap(A[i], A[A[i]])
    end while

// Identify duplicates based on A[i] != i
for i = 0 to n - 1:
    if A[i] != i:
        print A[i]
    end if
end for

Insight:
Algoritma memanfaatkan fakta bahawa setiap elemen dalam tatasusunan sepatutnya berada pada indeksnya. Ia menggunakan elemen tatasusunan untuk mencipta pilih atur, memastikan elemen yang wujud akan dipetakan ke indeksnya yang betul. Gelung pertama berulang melalui tatasusunan dan memastikan setiap elemen mencapai indeks yang dimaksudkan melalui swap.

Penjelasan:
Gelung pertama mengubah suai tatasusunan supaya bagi mana-mana elemen x, jika ia muncul sekurang-kurangnya sekali, satu kejadian akan berada pada indeks A[x]. Dalam setiap swap, entri yang sepadan dengan elemen yang salah diperbetulkan, menjamin bahawa jumlah bilangan swap dihadkan oleh bilangan elemen, N-1.

Gelung kedua mengenal pasti pendua dengan mencetak indeks setiap elemen yang tidak sepadan dengan indeksnya, menunjukkan ketiadaannya dalam tatasusunan asal.

Kesimpulan:
Algoritma ini cekap mengenal pasti elemen pendua dalam tatasusunan dengan menggunakan tatasusunan input dengan bijak sendiri. Masa O(n) dan kerumitan ruang O(1) menjadikannya sesuai untuk pelbagai aplikasi praktikal.

Atas ialah kandungan terperinci Bagaimana Mencari Pendua dalam Tatasusunan dengan Kerumitan Masa dan Ruang Optimum?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!