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 && H

    Weiter 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.


Anmelden zum Antworten