zwei Arrays mergen
-
Hallo Leute,
ich wollte wissen, wie man zwei aufsteigend sortierte Arrays ohne Duplikate merged.
Ich will dafür einen Pseudocode erstellen.
Ich hätte folgenden Ansatz:Merge(int []A,int []B)
int [A.length + B.length] H
pos,a_pos_a,pos_b = 1
unique_value = 0
while a_pos < A length && b_pos < B.length do
H[pos ++] = A[a_pos] < B[b_pos] ? A[a_pos++] : B[b_pos++]
unique_value += (pos <= 2 || H[pos -1] != H[pos - 2] )
int[unique value ] C
for i = 1 to H.length do
if i > 2 && HWeiter bin ich bis jetzt leider nicht gekommen.
Vielen Dank im Voraus !
-
@JohannesK Das sieht mehr Pseudo als Code aus. Ich weiß nicht, was das bedeuten soll. Warum stellst du eine Frage zu Pseudocode unter C++?
-
Sorry mein Fehler
-
@JohannesK Dein Pseudocode ist ziemlich schwer zu lesen. Versuch' es doch mal in natürlicher Sprache in eigenen Worten.
-
Sind die Arrays A und B ohne Duplikate?
Ansonsten sieht dein Ansatz tendenziell nicht schlecht aus, mal in Worten zusammengefasst wie ich ihn verstehe und ergänzen würde:
- Iteriere solange bis A oder B durchlaufen ist
- Vergleiche das Element i in A und B und wähle das kleinere aus
- Move den pos pointer in dem entsprechenden Array weiter, wo das Element ausgewählt worden ist (Nicht in beiden, was du bisher machst)
- Prüfe, ob das ausgewählte Element das selbe ist, was du letze Runde augewählt hat d.h. H[pos_h - 1] == element (dann ist es ein Duplikat) -> Hier musst du dir was für den ersten Durchgang noch überlegen
- Füge das Element dem Array H hinzu, wenn es kein Duplikat ist (und pos pointer vorwärts bewegen)
- Iteriere über A (mit pos_a als startpunkt) bis Ende
- Füge das Element von A in H ein (pos_a und pos_h erhöhen)
- Iteriere über B (mit pos_b als startpunkt) bis Ende
- Füge das Element von B in H ein (pos_b und pos_h erhöhen)
Das heißt du hast insgesamt drei Schleifen
Logisch sollte aber sein, dass einer der letzen Schleifen beiden Schleifen nicht ausgeführt wird, denn eines der beiden Arrays muss durch Schleife 1 ja schon fertig durchlaufen sein.
- Iteriere solange bis A oder B durchlaufen ist
