Buang Pendua di Tempat Asal
Gunakan sepasang penuding perlahan dan pantas.
Buang Pendua di Tempat Asal ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 3 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Buang Pendua di Tempat Asal
Diberikan tatasusunan tersusun, simpan satu salinan bagi setiap nilai tanpa menggunakan tatasusunan tambahan. Melakukannya di tempat asal menjimatkan memori dan merupakan soalan temu duga klasik. 🧹
Mengapa Susunan Membantu
Apabila tatasusunan tersusun, setiap pendua berada betul-betul di sebelah pasangannya. Jadi anda hanya perlu membandingkan jiran, bukan seluruh tatasusunan.
Dua Peranan, Dua Penuding
Gunakan penuding perlahan yang menandakan nilai terakhir yang disimpan dan penuding pantas yang mengimbas ke hadapan untuk mencari sesuatu yang baharu.
slow = 0
fast = 1Penuding Perlahan Menulis
Anggap penuding perlahan sebagai kedudukan penulisan: semua yang berada di kedudukan itu atau sebelumnya telah dibersihkan dan adalah unik.
Penuding Pantas Membaca
Penuding pantas hanya membaca ke hadapan. Ia bergerak jauh di hadapan dan hanya memberi isyarat kepada penuding perlahan apabila menemui nilai yang belum disimpan.
Langkau Ulangan
Jika a[fast] sama dengan a[slow], itu ialah ulangan, jadi jangan lakukan apa-apa selain memajukan fast. Pendua itu akan dilangkaui secara senyap.
for fast in range(1, n):
if a[fast] == a[slow]:
continueMenemui Sesuatu yang Baharu
Apabila a[fast] berbeza, gerakkan penuding perlahan ke hadapan dan salin nilai baharu ke situ. Ini menulis ganti pendua lama dengan data unik yang baharu.
else:
slow += 1
a[slow] = a[fast]Jawapannya ialah Panjang
Selepas imbasan, slow + 1 ialah bilangan nilai unik, yang semuanya terkumpul di bahagian hadapan tatasusunan.
return slow + 1Abaikan Bahagian Hujung
Apa sahaja yang berada selepas awalan unik itu ialah baki data yang tidak diperlukan. Masalah ini hanya mengambil kira slow + 1 unsur pertama, jadi biarkan bahagian hujung begitu sahaja.
Jangan Lupa Tatasusunan Kosong
Tatasusunan kosong mempunyai sifar nilai unik. Buat semakan untuk n == 0 sebelum bermula supaya anda tidak membaca melepasi hujung.
if n == 0:
return 0Satu Lintasan, Tiada Ruang Tambahan
Corak perlahan-pantas ini berjalan dalam masa O(n) dan menggunakan ruang tambahan O(1), tepat seperti yang diperlukan oleh had memori yang ketat.
Semakan Pantas
Anda membuang pendua di tempat asal pada tatasusunan tersusun dengan penuding perlahan dan pantas.
Ulang Kaji
Pada tatasusunan tersusun, pasangan penuding perlahan-pantas membuang pendua dalam satu lintasan O(n) tanpa ruang tambahan, lalu memulangkan slow + 1 sebagai bilangan nilai unik. 🎉
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Buang Pendua di Tempat Asal” percuma?
Ya — teks penuh “Buang Pendua di Tempat Asal” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Buang Pendua di Tempat Asal”?
Gunakan sepasang penuding perlahan dan pantas. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 3 daripada 4.
Berapa lamakah pelajaran “Buang Pendua di Tempat Asal” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Dua Penuding pada Tatasusunan Terisih
- Cari Pasangan dengan Jumlah Diberi
- Buang Pendua di Tempat Asal
- Cantumkan Dua Jujukan Terisih