Perkara yang dinilai oleh penemu duga
Diberikan tatasusunan integer yang mungkin mengandungi pendua, ubah ia secara in-place kepada pilihatur leksikografi seterusnya yang lebih besar secara ketat; jika susunan semasa adalah maksimum, hasilkan pilihatur menaik yang terkecil.
Kekangan dan batas sempadan
- Gunakan ruang tambahan O(1) dan hanya pertukaran (swap) atau penyongsangan (reverse).
- Nilai pendua bukan identiti yang berbeza, tetapi perbandingan adalah secara numerik.
- Tatasusunan kosong dan satu elemen kekal tidak berubah.
- Hasil mestilah pilihatur leksikografi yang bersebelahan secara global, bukan pertukaran tempatan yang sewenang-wenangnya.
Cari pivot paling kanan
Imbas dari kanan untuk indeks pertama i di mana nilai kiri adalah kurang secara ketat daripada nilai kanan. Akhiran (suffix) sudah pun tidak menaik. Jika tiada pivot wujud, keseluruhan tatasusunan adalah maksimum; songsangkannya untuk mendapatkan pilihatur minimum.
Tukar dan minimumkan akhiran
Dengan adanya pivot, imbas dari kanan untuk mencari nilai pertama yang lebih besar daripada nums[i]. Oleh kerana akhiran adalah tidak menaik, calon pertama tersebut ialah nilai lebih besar yang paling kecil yang boleh dilaksanakan. Tukarkannya dengan pivot, kemudian songsangkan akhiran selepas i untuk menjadikannya menaik.
Rangka kerja jawapan 30 saat
“Imbas dari kanan untuk pivot menaik yang pertama i. Jika tiada, songsangkan tatasusunan menurun yang maksimum. Jika ada, cari nilai paling kanan yang lebih besar daripada nums[i], tukarkan mereka, dan songsangkan akhiran. Akhiran bermula dengan susunan pada arah bertentangan, jadi ini menghasilkan peningkatan terkecil yang mungkin dalam masa O(n) dan ruang O(1).”
Soalan penjelasan sebelum menjawab
- Adakah mutasi mesti secara in-place? Ruang tambahan akan membolehkan pengisihan salinan, manakala in-place memerlukan penyongsangan.
- Adakah susunan leksikografi berasaskan numerik atau rentetan? Nilai negatif dan berbilang digit adalah berbeza.
- Bolehkah nilai berulang? Nilai pendua memerlukan perbandingan ketat untuk kedua-dua pivot dan calon pertukaran.
Perincian langkah demi langkah
Untuk [1,2,3], pivot pada 1 bertukar dengan nilai akhiran lebih besar yang terkecil 2, menghasilkan [2,1,3] selepas penyongsangan akhiran. Untuk [3,2,1], tiada pivot wujud, jadi penyongsangan menghasilkan [1,2,3].
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
swap(nums[i], nums[j])
reverse(nums, i + 1, n - 1)Gunakan “lebih besar daripada atau sama dengan” semasa melangkau calon pivot dan “kurang daripada atau sama dengan” semasa melangkau calon pertukaran, bagi memastikan peningkatan yang ketat. Lakukan penyongsangan dan bukannya pengisihan kerana akhiran sudah teratur, jadi penyongsangan kekal linear dan in-place.
Model jawapan berkualiti tinggi
“Pilihatur seterusnya mengubah kedudukan paling kanan yang mungkin dan menjadikan segala-galanya selepasnya sekecil mungkin. Saya mencari pivot paling kanan di mana nilai kiri adalah kurang secara ketat daripada nilai kanan, menukarnya dengan nilai paling kanan yang lebih besar daripadanya, dan menyongsangkan akhiran. Tiada pivot bermakna tatasusunan adalah maksimum, jadi saya menyongsangkan keseluruhan tatasusunan. Pengimbasan dan penyongsangan adalah O(n) dan algoritma ini menggunakan pemboleh ubah tambahan yang malar.”
Kesilapan lazim
- Mencari pivot dari kiri dan mengubah kedudukan tertib lebih tinggi.
- Berhenti selepas pertukaran tanpa meminimumkan akhiran.
- Menggunakan lebih besar atau sama dengan untuk calon pertukaran, menyebabkan pendua gagal meningkat secara ketat.
- Memanggil isih umum pada akhiran dan melanggar kekangan in-place.
- Mengembalikan tatasusunan menurun tanpa perubahan apabila ia sepatutnya kembali ke susunan minimum.
Gejala kegagalan dan pembaikan
Jika [1,3,2] menjadi [3,1,2], pivot berada terlalu jauh ke kiri; hasil yang betul ialah [2,1,3]. Jika [1,1,5] menukar nilai yang sama, sempadan perbandingan ketat adalah salah.
Pelaksanaan produksi
Terima jujukan capaian rawak yang boleh diubah suai dan songsangkan dengan dua penunjuk. Jika perbandingan boleh melimpah (overflow) atau susunan bahasa berbeza, tentukan pembanding dan dasar input tidak sah pada sempadan antara muka.
Senarai semak pengesahan
Uji tatasusunan kosong, satu elemen, menaik, menurun, pendua, pivot pada hujung, dan beberapa nilai optimum yang sama. Untuk tatasusunan kecil, jana semua pilihatur yang berbeza, susun secara leksikografi, dan sahkan bahawa fungsi mengembalikan item seterusnya atau kembali ke item pertama.
Soalan susulan dan jawapan
Mengapakah pivot mesti yang paling kanan?
Pivot yang lebih ke kanan mengubah kedudukan tertib yang lebih rendah. Memilih nilai lebih besar terkecil yang boleh dilaksanakan dan meminimumkan akhirannya akan menghasilkan pilihatur bersebelahan dan bukannya melangkau susunan yang sah.
Mengapakah akhiran boleh disongsangkan secara terus?
Imbasan pivot dari kanan ke kiri membuktikan bahawa akhiran adalah tidak menaik. Selepas pertukaran, menyongsangkannya memulihkan susunan menaik terkecil tanpa pengisihan umum.
Bagaimana pula dengan pilihatur seterusnya yang ke-k?
Mengulangi operasi ini menelan kos O(k n). Bagi k yang besar, pendekatan pangkat/nyahpangkat (rank/unrank) atau pengiraan boleh melompat secara terus, tetapi ia memerlukan pengiraan gabungan dan pengendalian pendua.
Rubrik pemarkahan
- Pivot: mencari kenaikan ketat yang paling kanan.
- Pertukaran: memilih nilai pertama yang lebih besar secara ketat dari kanan.
- Akhiran: menyongsangkannya ke dalam susunan menaik terkecil.
- Sempadan: merangkumi tatasusunan menurun, pendua, kosong, dan satu elemen.
- Kerumitan: memberikan masa O(n) dan ruang tambahan O(1).
Pemeriksaan pematuhan
Sahkan bahawa ketiga-tiga langkah, contoh sempadan, dan tuntutan kerumitan kekal konsisten.
Senarai semak jawapan temu duga
Terangkan perubahan terkecil sebelah kanan, tulis pivot, pertukaran dan penyongsangan, gunakan contoh pendua untuk perbandingan ketat, kemudian berikan kerumitan dan ujian pilihatur kecil yang menyeluruh.
Rumusan satu ayat
Pilihatur seterusnya ditemui secara in-place melalui pivot paling kanan, pertukaran lebih besar terkecil yang boleh dilaksanakan, dan penyongsangan akhiran dalam masa linear.