Temukan "lubang" dalam daftar angka

Apa cara tercepat untuk menemukan bilangan bulat (terkecil) pertama yang tidak ada dalam daftar bilangan bulat yang tidak disortir (dan itu lebih besar dari nilai terkecil daftar)?

Pendekatan primitif saya adalah menyortir mereka dan masuk daftar, apakah ada cara yang lebih baik?

Dengan asumsi bahwa yang Anda maksud adalah "bilangan bulat" ketika Anda mengatakan "angka", Anda dapat menggunakan bitvector ukuran 2 ^ n, di mana n adalah jumlah elemen (katakanlah rentang Anda termasuk bilangan bulat antara 1 dan 256, maka Anda dapat menggunakan 256- bit, atau 32 byte, bitvector). Ketika Anda menemukan bilangan bulat di posisi n rentang Anda, atur bit ke-n.

Ketika Anda selesai menghitung koleksi bilangan bulat, Anda beralih pada bit di bitvector Anda, mencari posisi bit yang ditetapkan 0. Mereka sekarang cocok dengan posisi n dari bilangan bulat Anda yang hilang.

Ini adalah O (2 * N), oleh karena itu O (N) dan mungkin lebih hemat memori daripada menyortir seluruh daftar.

Jika Anda mengurutkan seluruh daftar terlebih dahulu, maka Anda menjamin run-time terburuk. Selain itu, pilihan Anda untuk mengurutkan algoritma sangat penting.

Inilah cara saya mendekati masalah ini:

1. Gunakan tumpukan , fokus pada elemen terkecil dalam daftar.
2. Setelah setiap swap, lihat apakah Anda memiliki celah.
3. Jika Anda menemukan celah, maka return: Anda telah menemukan jawaban Anda.
4. Jika Anda tidak menemukan celah, lanjutkan bertukar.

Berikut ini visualisasi dari heap sort .

Hanya untuk menjadi esoteris dan "pintar", dalam kasus khusus array yang hanya memiliki satu "lubang", Anda dapat mencoba solusi berbasis XOR:

• Tentukan rentang array Anda; ini dilakukan dengan mengatur variabel "max" dan "min" ke elemen pertama array, dan untuk setiap elemen setelah itu, jika elemen itu kurang dari min atau lebih besar dari max, atur min atau max ke nilai baru.
• Jika kisaran satu kurang dari kardinalitas set, hanya ada satu "lubang" sehingga Anda dapat menggunakan XOR.
• Inisialisasi variabel integer X ke nol.
• Untuk setiap bilangan bulat dari min hingga maksimum secara inklusif, XOR menghargai dengan X dan menyimpan hasilnya dalam X.
• Sekarang XOR masing-masing integer dalam array dengan X, menyimpan setiap hasil berturut-turut ke X seperti sebelumnya.
• Setelah selesai, X akan menjadi nilai "lubang" Anda.

Ini akan berjalan kira-kira 2N waktu yang mirip dengan solusi bitvector, tetapi membutuhkan lebih sedikit ruang memori untuk setiap ukuran N> Namun, jika array memiliki beberapa "lubang", X akan menjadi "jumlah" XOR dari semua lubang, yang akan sulit atau tidak mungkin untuk dipisahkan ke dalam nilai lubang yang sebenarnya. Jika demikian, Anda kembali ke metode lain seperti pendekatan "pivot" atau "bitvector" dari jawaban lain.

Anda bisa mengulang ini juga menggunakan sesuatu yang mirip dengan metode pivot untuk lebih mengurangi kerumitan. Susun ulang susunan berdasarkan titik pivot (yang akan menjadi maks dari sisi kiri dan min kanan; akan sepele untuk menemukan maks dan min dari array penuh saat berputar). Jika sisi kiri pivot memiliki satu atau lebih lubang, rekur ulang hanya ke sisi itu; jika tidak berulang ke sisi lain. Di setiap titik di mana Anda dapat menentukan hanya ada satu lubang, gunakan metode XOR untuk menemukannya (yang secara keseluruhan harus lebih murah daripada terus berporos sampai ke kumpulan dua elemen dengan lubang yang dikenal, yang merupakan dasar kasus untuk algoritma pivot murni).

Berapa kisaran angka yang akan Anda temui? Jika rentang itu tidak terlalu besar, Anda bisa menyelesaikan ini dengan dua pemindaian (linear time O (n)) menggunakan array dengan elemen sebanyak jumlah angka, ruang perdagangan untuk waktu. Anda dapat menemukan rentang secara dinamis dengan satu pemindaian lagi. Untuk mengurangi ruang, Anda dapat menetapkan 1 bit untuk setiap angka, memberi Anda penyimpanan bernilai 8 angka per byte.

Pilihan Anda yang lain yang mungkin lebih baik untuk skenario awal dan akan menjadi insitu daripada menyalin memori adalah untuk memodifikasi jenis seleksi untuk berhenti lebih awal jika min ditemukan dalam pass pemindaian tidak 1 lebih dari min terakhir ditemukan.

Tidak terlalu. Karena nomor yang belum dipindai selalu bisa menjadi nomor yang mengisi "lubang" tertentu, Anda tidak dapat menghindari pemindaian setiap nomor setidaknya sekali dan kemudian membandingkannya dengan kemungkinan tetangga. Anda mungkin dapat mempercepat beberapa hal dengan membangun pohon biner atau lebih dan kemudian membaliknya dari kiri ke kanan hingga lubang ditemukan, tetapi itu pada dasarnya memiliki kompleksitas waktu yang sama dengan penyortiran, karena penyortiran. Dan Anda mungkin tidak akan menghasilkan sesuatu yang lebih cepat dari Timsort .

Sebagian besar ide di sini tidak lebih dari sekadar penyortiran. Versi bitvector adalah Bucketsort biasa. Heap sort juga disebutkan. Ini pada dasarnya bermula untuk memilih algoritma pengurutan yang tepat yang tergantung pada persyaratan waktu / ruang dan juga pada kisaran dan jumlah elemen.

Dalam pandangan saya, menggunakan struktur tumpukan mungkin adalah solusi yang paling umum (tumpukan pada dasarnya memberi Anda elemen terkecil secara efisien tanpa jenis lengkap).

Anda juga bisa menganalisis pendekatan yang menemukan angka terkecil terlebih dahulu dan kemudian memindai setiap bilangan bulat lebih besar dari itu. Atau Anda menemukan 5 angka terkecil berharap akan ada celah.

Semua algoritma ini memiliki kekuatan mereka tergantung pada karakteristik input dan persyaratan program.

Solusi yang tidak menggunakan penyimpanan tambahan atau menganggap lebar (32 bit) bilangan bulat.

1. Dalam satu lintasan linear, temukan angka terkecil. Mari kita sebut ini "min". O (n) kompleksitas waktu.

2. Pilih elemen pivot acak dan lakukan partisi gaya quicksort.

3. Jika pivot berakhir di posisi = ("pivot" - "min"), kemudian muncul kembali di sisi kanan partisi, atau muncul lagi di sisi kiri partisi. Idenya di sini adalah bahwa jika tidak ada lubang dari awal, pivot akan berada pada posisi ("pivot" - "min"), sehingga lubang pertama harus terletak di sebelah kanan partisi dan sebaliknya.

4. Basis kasus adalah array dari 1 elemen dan lubang terletak di antara elemen ini dan yang berikutnya.

Total kompleksitas waktu berjalan yang diharapkan adalah O (n) (8 * n dengan konstanta) dan kasus terburuk adalah O (n ^ 2). Analisis kompleksitas waktu untuk masalah serupa dapat ditemukan di sini .

Saya percaya saya telah datang dengan sesuatu yang harus bekerja secara umum dan efisien jika Anda dijamin tidak memiliki duplikat * (namun, itu harus diperluas ke sejumlah lubang dan berbagai bilangan bulat).

Gagasan di balik metode ini seperti quicksort, di mana kita menemukan pivot dan partisi di sekitarnya, kemudian muncul kembali pada sisi dengan lubang. Untuk melihat sisi mana yang memiliki lubang, kami menemukan angka terendah dan tertinggi, dan membandingkannya dengan pivot dan jumlah nilai di sisi itu. Katakanlah pivot adalah 17 dan angka minimum adalah 11. Jika tidak ada lubang, harus ada 6 angka (11, 12, 13, 14, 15, 16, 17). Jika ada 5, kita tahu ada lubang di sisi itu dan kita bisa melihat lagi di sisi itu untuk menemukannya. Saya kesulitan menjelaskannya lebih jelas dari itu, jadi mari kita ambil contoh.

15 21 10 13 18 16 22 23 24 20 17 11 25 12 14

Poros:

10 13 11 12 14 |15| 21 18 16 22 23 24 20 17 25

15 adalah pivot, ditunjukkan oleh pipa ( ||). Ada 5 angka di sisi kiri pivot, karena harus ada (15 - 10), dan 9 di kanan, di mana harus ada 10 (25 - 15). Jadi kita berulang di sisi kanan; kami akan mencatat bahwa batas sebelumnya adalah 15 jika lubang berdekatan (16).

[15] 18 16 17 20 |21| 22 23 24 25

Sekarang ada 4 angka di sisi kiri tetapi harus ada 5 (21 - 16). Jadi kita mengulanginya di sana, dan sekali lagi kita akan perhatikan ikatan sebelumnya (dalam kurung).

[15] 16 17 |18| 20 [21]

Sisi kiri memiliki 2 angka yang benar (18 - 16), tetapi kanan memiliki 1 bukan 2 (20 - 18). Bergantung pada kondisi akhir kami, kami dapat membandingkan 1 angka dengan dua sisi (18, 20) dan melihat bahwa 19 hilang atau berulang sekali lagi:

[18] |20| [21]

Sisi kiri memiliki ukuran nol, dengan celah antara pivot (20) dan ikatan sebelumnya (18), jadi 19 adalah lubangnya.

*: Jika ada duplikat, Anda mungkin bisa menggunakan hash set untuk menghapusnya dalam waktu O (N), menjaga metode keseluruhan O (N), tetapi itu mungkin membutuhkan waktu lebih lama daripada menggunakan beberapa metode lain.