Keresse meg a legkisebb hiányzó egész számot egy tömbben
1. Áttekintés
Ebben az oktatóanyagban különböző algoritmusokat fogunk látni, amelyek lehetővé teszik számunkra, hogy megtaláljuk a legkisebb hiányzó pozitív egész számot egy tömbben.
Először végigmegyünk a probléma magyarázatán. Ezt követően három különböző algoritmust fogunk látni, amelyek megfelelnek az igényeinknek. Végül megbeszéljük összetettségüket.
2. A probléma magyarázata
Először magyarázzuk el, mi az algoritmus célja. Meg akarjuk keresni a legkisebb hiányzó pozitív egész számot egy pozitív egész tömbben. Vagyis egy tömbben x elemek között keresse meg a legkisebb elemet 0 és x - 1 ez nincs a tömbben. Ha a tömb mindet tartalmazza, akkor a megoldás az x, a tömb mérete.
Vegyük például a következő tömböt: [0, 1, 3, 5, 6]. Megvan 5 elemek. Ez azt jelenti, hogy a legkisebb egész számot keressük 0 és 4 ez nincs ebben a tömbben. Ebben a konkrét esetben az 2.
Képzeljünk el egy másik tömböt: [0, 1, 2, 3]. Ahogy van 4 elemek között egész számot keresünk 0 és 3. Egyik sem hiányzik, így a legkisebb egész szám, amely nincs a tömbben 4.
3. Rendezett tömb
Most nézzük meg, hogyan lehet megtalálni a legkisebb hiányzó számot egy rendezett tömbben. Rendezett tömbben a legkisebb hiányzó egész szám lenne az első index, amely nem tartja magát értékként.
Vegyük fontolóra a következő rendezett tömböt: [0, 1, 3, 4, 6, 7]. Most nézzük meg, melyik érték melyik indexnek felel meg:
Index: 0 1 2 3 4 5 Érték: 0 1 3 4 6 7Mint láthatjuk, az értékindex nem tartalmaz egész számot 2, ebből kifolyólag 2 a legkisebb hiányzó egész szám a tömbben.
Mit szólnál ennek az algoritmusnak a Java-ban történő megvalósításához? Hozzunk létre először egy osztályt SmallestMissingPositiveInteger módszerrel searchInSortedArray ():
public class SmallestMissingPositiveInteger {public static int searchInSortedArray (int [] input) {// ...}}Most iterálhatunk a tömbön és keresse meg az első indexet, amely nem tartalmazza önmagát értékként és eredményül adja vissza:
for (int i = 0; i <input.length; i ++) {if (i! = input [i]) {return i; }}Végül, ha hiányzó elem megtalálása nélkül teljesítjük a ciklust, vissza kell adnunk a következő egész számot, amely a tömb hossza, ahogy az indexnél kezdjük 0:
visszatérő bemenet.hossz;Ellenőrizzük, hogy mindez a várt módon működik-e. Képzeljen el egy egész szám tömböt innen: 0 nak nek 5, a számmal 3 hiányzó:
int [] bemenet = új int [] {0, 1, 2, 4, 5};Ezután, ha az első hiányzó egész számra keresünk, 3 vissza kell adni:
int eredmény = SmallestMissingPositiveInteger.searchInSortedArray (input); assertThat (eredmény) .isEqualTo (3);De ha hiányzó számot keresünk egy tömbben hiányzó egész szám nélkül:
int [] bemenet = új int [] {0, 1, 2, 3, 4, 5};Megállapítjuk, hogy az első hiányzó egész szám az 6, amely a tömb hossza:
int eredmény = SmallestMissingPositiveInteger.searchInSortedArray (input); assertThat (eredmény) .isEqualTo (input.hossz);Ezután meglátjuk, hogyan kell kezelni a nem rendezett tömböket.
4. Válogatás nélküli tömb
Szóval, mi a helyzet a legkisebb hiányzó egész szám megtalálásával egy rendezetlen tömbben? Többféle megoldás létezik. Az első az, hogy először egyszerűen rendezni kell a tömböt, majd újra fel kell használni előző algoritmusunkat. Egy másik megközelítés az lenne, ha egy másik tömböt használnánk a jelenlévő egész számok megjelölésére, majd az adott tömb bejárásával megtalálnánk az első hiányzó számot.
4.1. Először a tömb rendezése
Kezdjük az első megoldással, és hozzunk létre egy újat searchInUnsortedArraySortingFirst () módszer.
Tehát újra felhasználjuk algoritmusunkat, de először rendeznünk kell a bemeneti tömböt. Ennek érdekében ki fogjuk használni Tömbök. Rendezés ():
Tömbök.rendezés (bemenet);Ez a módszer a sorrend szerint rendezi a bemenetet. Egész számoknál ez a legkisebbtől a legnagyobbig terjed. Az algoritmusok rendezéséről további részletek találhatók a Java tömbök rendezéséről szóló cikkünkben.
Ezt követően meghívhatjuk algoritmusunkat a most rendezett bemenettel:
return searchInSortedArray (input);Ennyi, most ellenőrizhetjük, hogy minden a várt módon működik-e. Képzeljük el a következő tömböt válogatás nélküli egész számokkal és hiányzó számokkal 1 és 3:
int [] bemenet = új int [] {4, 2, 0, 5};Mint 1 a legkisebb hiányzó egész szám, azt várjuk, hogy a módszer meghívásának eredménye:
int eredmény = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst (input); assertThat (eredmény) .isEqualTo (1);Próbáljuk ki egy tömbön, hiányzó szám nélkül:
int [] bemenet = új int [] {4, 5, 1, 3, 0, 2}; int eredmény = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst (input); assertThat (eredmény) .isEqualTo (input.hossz);Ez az, az algoritmus visszatér 6, ez a tömb hossza.
4.2. Logikai tömb használata
Egy másik lehetőség az, hogy egy másik tömböt használunk, amely ugyanolyan hosszú, mint a bemeneti tömb logikai értékek, amelyek megmondják, hogy az indexnek megfelelő egész szám megtalálható-e a bemeneti tömbben, vagy sem.
Először hozzunk létre egy harmadik módszert, searchInUnsortedArrayBooleanArray ().
Ezután hozzuk létre a logikai tömböt, zászlók, és a bemeneti tömb minden egész számához, amely megfelel a logikai tömb, a megfelelő értéket beállítottuk igaz:
logikai [] zászlók = új logikai [bemenet.hossz]; for (int szám: bevitel) {if (szám <zászlók.hossz) {zászlók [szám] = igaz; }}Most, a mi zászlók tömb tart igaz a bemeneti tömbben lévő minden egész számra, és hamis másképp. Akkor megtehetjük iterálni a zászlók tömb és adja vissza az első indextartást hamis. Ha nincs, akkor visszaadjuk a tömb hosszát:
for (int i = 0; i <zászlók.hossz; i ++) {if (! zászlók [i]) {visszatér i; }} return flags.length;Ismét próbáljuk meg ezt az algoritmust a példáinkkal. Először újból felhasználjuk a hiányzó tömböt 1 és 3:
int [] bemenet = új int [] {4, 2, 0, 5};Akkor, amikor a legkisebb hiányzó egész számot keresjük új algoritmusunkkal, a válasz továbbra is az 1:
int eredmény = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray (input); assertThat (eredmény) .isEqualTo (1);És a teljes tömb esetében a válasz sem változik, és továbbra is az 6:
int [] bemenet = új int [] {4, 5, 1, 3, 0, 2}; int eredmény = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray (input); assertThat (eredmény) .isEqualTo (input.hossz);5. Bonyolultságok
Most, hogy áttekintettük az algoritmusokat, beszéljünk azok komplexitásáról, a Big O jelöléssel.
5.1. Válogatott tömb
Kezdjük az első algoritmussal, amelyhez a bemenet már rendezve van. Ebben az esetben a legrosszabb eset az, hogy nem talál hiányzó egész számot, és ezért bejárja a teljes tömböt. Ez azt jelenti, hogy lineáris komplexitásunk van, amelyet megjegyeznek Tovább), figyelembe véve n a bemenetünk hossza.
5.2. Válogatás nélküli tömb rendezési algoritmussal
Most vegyük fontolóra második algoritmusunkat. Ebben az esetben a bemeneti tömb nincs rendezve, és az első algoritmus alkalmazása előtt rendezzük. Itt, a bonyolultság a legnagyobb lesz a válogatási mechanizmus és az algoritmus bonyolultsága között.
A Java 11-től kezdve a Tömbök. Rendezés () A metódus kettős elfordítású gyors rendezési algoritmust használ a tömbök rendezéséhez. Ennek a rendezési algoritmusnak a bonyolultsága általában O (n log (n)), bár ez akár le is romolhat O (n²). Azt jelenti algoritmusunk bonyolultsága az lesz O (n log (n)) általában és a másodfokú bonyolultságig is degradálódhat O (n²).
Ez az idő bonyolultsága, de ne feledkezzünk meg a térről sem. Noha a keresési algoritmus nem foglal külön helyet, a rendezési algoritmus igen. A gyors rendezési algoritmus akár O (log (n)) a végrehajtás helye. Ezt érdemes figyelembe venni, amikor nagy tömbök algoritmusát választjuk.
5.3. Válogatás nélküli tömb logikai tömb
Végül nézzük meg, hogyan teljesít harmadik és egyben utolsó algoritmusunk. Ehhez nem rendezzük a bemeneti tömböt, ami azt jelenti nem szenvedjük el a válogatás bonyolultságát. Ami azt illeti, csak két tömböt haladunk át, mindkettő azonos méretű. Azt jelenti időbeli összetettségünk legyen O (2n), amely leegyszerűsítve Tovább). Ez jobb, mint az előző algoritmus.
De ami a tér összetettségét illeti, létrehozunk egy második tömböt, amely ugyanolyan méretű, mint a bemenet. Azt jelenti nekünk van Tovább) tér bonyolultsága, ami rosszabb, mint az előző algoritmus.
Mindezek ismeretében rajtunk múlik, hogy az igényeinknek legjobban megfelelő algoritmust válasszunk, attól függően, hogy milyen körülmények között fogjuk használni.
6. Következtetés
Ebben a cikkben algoritmusokat vizsgáltunk a tömb legkisebb hiányzó pozitív egész számának megtalálásához. Láttuk, hogyan lehet ezt elérni rendezett tömbben, valamint rendezetlen tömbben. Megbeszéltük a különböző algoritmusok idő- és térbonyolultságát is, lehetővé téve számunkra, hogy bölcsen válasszunk egyet az igényeinknek megfelelően.
Szokás szerint az ebben a cikkben bemutatott teljes kódpéldák elérhetők a GitHubon.
