Hogyan válasszuk ki a különböző elemek a tömb
Minta egyedi elemei egy tömb
H Adachi - kell egy rendezetlen tömb jelölje ki az összes egyedi elemekkel. Bonyolítja a feladat a következő: - Lehetőleg ne használja több memóriát, és egyedi elemeket ebbe a tömbbe.
A legegyszerűbb algoritmus: ezt a pontot, és hasonlítsa össze mindenkit. Mert a munka, meg kell két számláló először átlépi az elemek sorrendben a második halad minden elemét, és összehasonlítja azokat a jelenlegi.
Azonnal vegye figyelembe, hogy a változók mindig nem negatív. Ez vezet néhány jellemzőjét.
Most, ha megváltoztatjuk a tömb, és hagyjuk benne csak a különböző elemeket, hogy meg fog változni a mérete (a méret számát értjük a különböző elemek, a tényleges mérete nem fog megváltozni), így a kezdeti méret a tömb által elfogadott mutató. Ugyanez a mutató tárolja az elemek száma átalakítás után.
A lényege az algoritmus: veszünk egy elemet, és látni, hogy ugyanazokat az elemeket hozzá. Ha nem, akkor másolja az elemet, és ha igen, folytassa a következő tételt. Másolásához, be Pos - számos talált különböző elemeit a tömb.
és egy egyedi zászló, jelezve, hogy az aktuális elem nem esik egybe sem őket már jelen vannak a tömbben.
Self-vizsgálati ciklus
A ciklus a ciklusban komplexitás n-edrendű 2. Ez az algoritmus fenntartja a elemek sorrendje. A kis tömbök, ez az algoritmus gyorsabb lesz, mint a többi, mert az egyszerűség.
Vannak gyorsabb algoritmusok. Ha veszel egy rendezett tömbben vannak elemét azonos egymás mellé. Akkor egy változó előző, amely tárolja a korábbi érték a tömb elem. Ha az aktuális elem dok, hagyja, de ha nem, akkor másolja és módosítsa az értéket a prev érték az aktuális elem.
Mivel fogunk egy szabványos gyors válogatás, mi is kell akkora egyik eleme, és az összehasonlító függvényt elemekkel.
Algoritmus tölt átlagosan n ∙ log (n) + válogató egyetlen áthaladnak a tömb (több n), azaz a komplexitása érdekében n + n ∙ log (n). Azonban nem szabad elfelejtenünk, hogy quicksort kis tömbben nem hatékony, így kis tömbben ez az algoritmus lassabb, mint a másodfokú.
Alapuló módszerek számlálás
I f számosságának elemek kicsi (néhány különböző elemek), akkor számíthatunk az előfordulások számát. Ez különösen akkor hasznos, ha előre ismert minden lehetséges elemet. Például, hogy megtalálják a különböző betűket. Mivel a számos különböző szimbólumok (a mi esetünkben) nem több, mint 256, akkor létre lehet hozni egy sor 256 elemek, nullával egyenlő.
A numerikus karakterből álló kódot indexként, és növeli az értékét a megfelelő elem.
Amikor több elemek jól ismertek, tipikusan egy speciális adatszerkezet, amely lehetővé teszi, hogy gyorsan hozzá elemeket, és ellenőrizze az előfordulása, például, szótár. kivonatolt kivonatolt tömb vagy asszociatív tömb.
ru-Cyrl 18- bemutató Sypachev S. S. 1989/04/14 [email protected] Stepan Sypachev diákok