Wie füge ich zwei sortierte Arrays zu einem sortierten Array zusammen? [geschlossen]

160

Dies wurde von mir in einem Interview verlangt und dies ist die Lösung, die ich bereitgestellt habe:

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length)
    {
        if (a[i] < b[j])
        {
            answer[k] = a[i];
            i++;
        }
        else
        {
            answer[k] = b[j];
            j++;
        }
        k++;
    }

    while (i < a.length)
    {
        answer[k] = a[i];
        i++;
        k++;
    }

    while (j < b.length)
    {
        answer[k] = b[j];
        j++;
        k++;
    }

    return answer;
}

Gibt es einen effizienteren Weg, dies zu tun?

Bearbeiten: Methoden mit korrigierter Länge.

Behrooz Karjoo
quelle
30
Sieht nach einer ziemlich guten Antwort für mich aus. Dieses Problem hat bestenfalls eine O (n) -Komplexität, und Ihre Antwort erreicht dies. Alles andere wird Mikrooptimierung sein.
Drew Hall
3
Gut gemacht! Dies ist im Wesentlichen ein Teil der Zusammenführungssortierung: Zusammenführen von zwei sortierten Streams (von Band oder Festplatte) zu einem anderen sortierten Stream.
Vladimir Dyuzhev
9
Hast du den Job?
Shai
5
Sie können auch den ternären Operator verwenden: while (i < a.length && j < b.length) answer[k++] = a[i] < b[j] ? a[i++] : b[j++]; Java-Sprachspezifikation: Bedingter Operator? : .
Anton Dozortsev
1
Du hast vergessen zu kommentieren !!!
LiziPizi

Antworten:

33

Eine kleine Verbesserung, aber nach der Hauptschleife können Sie System.arraycopydas Ende eines der Eingabearrays kopieren, wenn Sie am Ende des anderen angelangt sind. Dies ändert jedoch nichts an den O(n)Leistungsmerkmalen Ihrer Lösung.

Greg Hewgill
quelle
109
public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length)  
       answer[k++] = a[i] < b[j] ? a[i++] :  b[j++];

    while (i < a.length)  
        answer[k++] = a[i++];

    while (j < b.length)    
        answer[k++] = b[j++];

    return answer;
}

Ist etwas kompakter aber genau gleich!

Mike Saull
quelle
Für die Person, die sagte, dass dies einen Index außerhalb der Grenzen verursacht hat, welche Eingaben verwenden Sie? Es funktioniert in allen Fällen für mich.
Mike Saull
1
Verwenden Sie eine for-Schleife, um die Zeilen zusammenzuführen, in denen die Schleifenvariablen und die Schleifensteuerung deklariert sind. Verwenden Sie doppelte Leerzeilen sparsam - sieht zwischen den symmetrischen "Endkopien" unangebracht aus.
Graubart
58

Ich bin überrascht, dass niemand diese viel coolere, effizientere und kompaktere Implementierung erwähnt hat:

public static int[] merge(int[] a, int[] b) {
    int[] answer = new int[a.length + b.length];
    int i = a.length - 1, j = b.length - 1, k = answer.length;

    while (k > 0)
        answer[--k] =
                (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
    return answer;
}

Punkte von Interessen

  1. Beachten Sie, dass es die gleiche oder eine geringere Anzahl von Operationen ausführt als jeder andere O (n) -Algorithmus, jedoch in buchstäblich einer einzelnen Anweisung in einer einzelnen while-Schleife!
  2. Wenn zwei Arrays ungefähr gleich groß sind, ist die Konstante für O (n) gleich. Wenn Arrays jedoch wirklich unausgeglichen sind, System.arraycopywürden Versionen mit gewinnen, da dies intern mit einer einzelnen x86-Assemblyanweisung möglich ist.
  3. Beachten Sie a[i] >= b[j]statt a[i] > b[j]. Dies garantiert "Stabilität", die definiert ist als wenn Elemente von a und b gleich sind, wir wollen Elemente von a vor b.
Shital Shah
quelle
Dies ist ein wirklich sehr schöner Ansatz. Ich hatte Probleme, gute Benchmarks für meine Merge-Sortieralgorithmen in Swift lang zu erhalten. Die Konvertierung gab mir das, was ich brauchte, vielen Dank
Chackle
Was ist der Punkt von (j <0) in der while-Schleife? Übrigens, +1, das ist wirklich cool! Danke für das Teilen.
Hengameh
2
@Hengameh für den Fall j < 0, bist bereits erschöpft, so dass wir weiterhin die restlichen aElemente zum answer Array hinzufügen
Natan Streppel
6
Zu "klug" und in meinen Gedanken schwer zu lesen. Ich bevorzuge einfach zu lesenden Code, zumal Sie mit diesem Code nicht wirklich eine Leistungsverbesserung erzielen.
Kevin M
1
Pluspunkt für Hinweis und a [i]> = b [j] anstelle von a [i]> b [j]. Dies garantiert "Stabilität"
Yan Khonski
16

Alle Verbesserungen, die vorgenommen werden könnten, wären Mikrooptimierungen. Der Gesamtalgorithmus ist korrekt.

ChrisH
quelle
Wenn a groß und b klein ist, ist dieser Algorithmus falsch.
Jack
7
Es ist nicht falsch, aber nicht effizient.
Jack
@jack Wie kannst du es schneller als O (n) machen, wenn du ein Array von n Gegenständen produzierst?
Will
@will System.arrayCopy()ist dumm schnell, da es CPU-optimierte memcpyAufrufe verwendet. Es besteht also die Möglichkeit, die Leistung durch Kopieren von Blöcken zu verbessern. Es gibt auch Möglichkeiten für die binäre Suche nach den Grenzen.
schlank
Besonders wenn Sie die sortierte Natur verwenden können, um die meisten Einträge zu überspringen und sie niemals zu vergleichen. Sie können tatsächlich O (n) schlagen.
Tatarize
10

Diese Lösung ist auch anderen Posts sehr ähnlich, außer dass sie System.arrayCopy verwendet, um die verbleibenden Array-Elemente zu kopieren.

private static int[] sortedArrayMerge(int a[], int b[]) {
    int result[] = new int[a.length +b.length];
    int i =0; int j = 0;int k = 0;
    while(i<a.length && j <b.length) {
        if(a[i]<b[j]) {
            result[k++] = a[i];
            i++;
        } else {
            result[k++] = b[j];
            j++;
        }
    }
    System.arraycopy(a, i, result, k, (a.length -i));
    System.arraycopy(b, j, result, k, (b.length -j));
    return result;
}
Pani Dhakshnamurthy
quelle
7

Hier ist die Funktion aktualisiert. Es werden Duplikate entfernt, hoffentlich findet jemand dies verwendbar:

public static long[] merge2SortedAndRemoveDublicates(long[] a, long[] b) {
    long[] answer = new long[a.length + b.length];
    int i = 0, j = 0, k = 0;
    long tmp;
    while (i < a.length && j < b.length) {
        tmp = a[i] < b[j] ? a[i++] : b[j++];
        for ( ; i < a.length && a[i] == tmp; i++);
        for ( ; j < b.length && b[j] == tmp; j++);
        answer[k++] = tmp;
    }
    while (i < a.length) {
        tmp = a[i++];
        for ( ; i < a.length && a[i] == tmp; i++);
        answer[k++] = tmp;
    }
    while (j < b.length) {
        tmp = b[j++];
        for ( ; j < b.length && b[j] == tmp; j++);
        answer[k++] = tmp;
    }
    return Arrays.copyOf(answer, k);
}
vitali_y
quelle
+1, Danke fürs Teilen. Eine Frage: Warum haben Sie den Typ des Arrays und den Typ der Variablen 'temp' long ausgewählt?
Hengameh
(Ich habe Zweifel über den Methodennamen.)
Greybeard
5

Dies kann in 4 Anweisungen wie folgt erfolgen

 int a[] = {10, 20, 30};
 int b[]= {9, 14, 11};
 int res[]=new int[a.legth+b.length]; 
 System.arraycopy(a,0, res, 0, a.length); 
 System.arraycopy(b,0,res,a.length, b.length);
 Array.sort(res)

Sudhir
quelle
5
Ich verstehe nicht, warum diese Antwort negative Stimmen erhielt. Es ist wahr, dass es nicht effizient ist. Aber manchmal ist alles, was Sie brauchen, um die Arbeit so schnell wie möglich zu erledigen. Wenn Sie mit sehr kleinen Arrays arbeiten, beispielsweise mit weniger als 100 Elementen, würde ich lieber den obigen Code verwenden, als einen langen Code zu schreiben, der keine wichtigen Leistungsverbesserungen bewirkt. Vielen Dank an Sudhir für die Bereitstellung dieser einfachen Lösung und an SANN3 für die Bearbeitung.
Ahmedov
2
Die ungeschriebene Voraussetzung ist, dass eine sortFunktion sich nicht als Sortiermethode verwenden kann. Das wäre unendliche Regression statt Rekursion. Die andere Voraussetzung ist auch, dass merge_array die Funktion ist, die sort implementiert. Daher ist diese Antwort im wahrscheinlichsten Zusammenhang unbrauchbar.
Aki Suihkonen
In der gestellten Frage wurde nicht erwähnt, dass der erforderliche Code nur für kleine Arrays gilt. Diese Antwort wäre also irreführend, wenn sie nicht klar ihre Einschränkung darlegen würde. Schauen Sie sich auch meine Antwort unten an. Es dauert die gleiche Anzahl von Zeilen, um effizienten Code zu schreiben, der für jede
Arraygröße
Die Frage besagte, dass die Arrays bereits in sortierter Reihenfolge sind. Wenn die Arrays sehr groß sein könnten, würde diese Lösung zum Stillstand kommen und eine schlechte Leistung erbringen. So sicher, dass Sie die erforderlichen Endergebnisse erhalten würden, aber die App würde nicht funktionieren und Sie würden den Job nicht bekommen, wenn ich ein Interview führen würde.
Kevin M
Die Funktion Array.sort () verwendet TimSort, das die sortierten Läufe sehr häufig findet und eine Zusammenführungssortierung auf sie anwendet. Seltsamerweise kann dieser Code nicht einmal als "nicht effizient" bezeichnet werden, da er aufgrund der sortierten Läufe tatsächlich in O (n) -Zeit beendet wird. Sie können eine Reihe von Benchmarks ausführen. Die Chancen stehen gut, dass der OP-Code ziemlich oft übertroffen wird.
Tatarize
4

Ich musste es in Javascript schreiben, hier ist es:

function merge(a, b) {
    var result = [];
    var ai = 0;
    var bi = 0;
    while (true) {
        if ( ai < a.length && bi < b.length) {
            if (a[ai] < b[bi]) {
                result.push(a[ai]);
                ai++;
            } else if (a[ai] > b[bi]) {
                result.push(b[bi]);
                bi++;
            } else {
                result.push(a[ai]);
                result.push(b[bi]);
                ai++;
                bi++;
            }
        } else if (ai < a.length) {
            result.push.apply(result, a.slice(ai, a.length));
            break;
        } else if (bi < b.length) {
            result.push.apply(result, b.slice(bi, b.length));
            break;
        } else {
            break;
        }
    }
    return result;
}
ebdr
quelle
4

Apache-Sammlungen unterstützen die Sortiermethode seit Version 4; Sie können dies mit der folgenden collateMethode tun :

org.apache.commons.collections4.CollectionUtils

Hier Zitat aus Javadoc:

collate(Iterable<? extends O> a, Iterable<? extends O> b, Comparator<? super O> c)

Fügt zwei sortierte Sammlungen aund beine sortierte Liste zu einer einzigen zusammen, sodass die Reihenfolge der Elemente gemäß Komparator c beibehalten wird.

Das Rad nicht neu erfinden! Dokumentreferenz: http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/CollectionUtils.html

Vlad
quelle
4

GallopSearch Merge: O (log (n) * log (i)) statt O (n)

Ich ging voran und implementierte den Vorschlag von Greybeard in den Kommentaren. Vor allem, weil ich eine hocheffiziente geschäftskritische Version dieses Codes brauchte.

  • Der Code verwendet eine GallopSearch, die O (log (i)) ist, wobei i der Abstand zum aktuellen Index ist, für den der relevante Index existiert.
  • Der Code verwendet eine binarySearch, nachdem die Galoppsuche den richtigen Bereich identifiziert hat. Da Galopp dies auf einen kleineren Bereich begrenzt hat, ist die resultierende binäre Suche auch O (log (i))
  • Der Galopp und das Zusammenführen werden rückwärts ausgeführt. Dies scheint nicht geschäftskritisch zu sein, ermöglicht jedoch das Zusammenführen von Arrays. Wenn in einem Ihrer Arrays genügend Platz zum Speichern der Ergebniswerte vorhanden ist, können Sie es einfach als Zusammenführungsarray und Ergebnisarray verwenden. In einem solchen Fall müssen Sie den gültigen Bereich innerhalb des Arrays angeben.
  • In diesem Fall ist keine Speicherzuweisung erforderlich (große Einsparungen bei kritischen Vorgängen). Es stellt einfach sicher, dass nicht verarbeitete Werte nicht überschrieben werden (was nur rückwärts möglich ist). Tatsächlich verwenden Sie für beide Eingaben und Ergebnisse dasselbe Array. Es wird keine negativen Auswirkungen haben.
  • Ich habe konsequent Integer.compare () verwendet, damit dies für andere Zwecke ausgeschaltet werden kann.
  • Es besteht die Möglichkeit, dass ich ein wenig vermasselt und Informationen, die ich zuvor bewiesen habe, nicht verwendet habe. Zum Beispiel die binäre Suche in einem Bereich von zwei Werten, für die bereits ein Wert geprüft wurde. Es könnte auch eine bessere Möglichkeit geben, die Hauptschleife anzugeben. Der Flip-C-Wert wäre nicht erforderlich, wenn sie nacheinander zu zwei Operationen kombiniert würden. Da Sie wissen, dass Sie jedes Mal das eine und das andere tun werden. Es gibt Platz für etwas Politur.

Dies sollte der effizienteste Weg sein, mit einer zeitlichen Komplexität von O (log (n) * log (i)) anstelle von O (n). Und Worst-Case-Zeitkomplexität von O (n). Wenn Ihre Arrays klumpig sind und lange Werteketten zusammen haben, wird dies jede andere Möglichkeit in den Schatten stellen, andernfalls ist es einfach besser als sie.

Es hat zwei Lesewerte am Ende des Zusammenführungsarrays und den Schreibwert innerhalb des Ergebnisarrays. Nachdem herausgefunden wurde, welcher Endwert geringer ist, wird eine Galoppsuche in diesem Array durchgeführt. 1, 2, 4, 8, 16, 32 usw. Wenn der Bereich gefunden wird, in dem der Lesewert des anderen Arrays größer ist. Es sucht binär in diesen Bereich (halbiert den Bereich, sucht die richtige Hälfte, wiederholt bis zum Einzelwert). Dann kopiert es Array diese Werte in die Schreibposition. Beachten Sie, dass die Kopie notwendigerweise so verschoben wird, dass sie nicht dieselben Werte aus beiden Lesearrays überschreiben kann (was bedeutet, dass das Schreibarray und das Lesearray identisch sein können). Es führt dann dieselbe Operation für das andere Array aus, von dem jetzt bekannt ist, dass es kleiner als der neue Lesewert des anderen Arrays ist.

static public int gallopSearch(int current, int[] array, int v) {
    int d = 1;
    int seek = current - d;
    int prevIteration = seek;
    while (seek > 0) {
        if (Integer.compare(array[seek], v) <= 0) {
            break;
        }
        prevIteration = seek;
        d <<= 1;
        seek = current - d;
        if (seek < 0) {
            seek = 0;
        }
    }
    if (prevIteration != seek) {
        seek = binarySearch(array, seek, prevIteration, v);
        seek = seek >= 0 ? seek : ~seek;
    }
    return seek;
}

static public int binarySearch(int[] list, int fromIndex, int toIndex, int v) {
    int low = fromIndex;
    int high = toIndex - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = list[mid];
        int cmp = Integer.compare(midVal, v);
        if (cmp < 0) {
            low = mid + 1;
        } else if (cmp > 0) {
            high = mid - 1;
        } else {
            return mid;// key found
        }
    }
    return -(low + 1);// key not found.
}

static public int[] sortedArrayMerge(int[] a, int[] b) {
    return sortedArrayMerge(null, a, a.length, b, b.length);
}

static public int[] sortedArrayMerge(int[] results, int[] a, int aRead, int b[], int bRead) {
    int write = aRead + bRead, length, gallopPos;
    if ((results == null) || (results.length < write)) {
        results = new int[write];
    }
    if (aRead > 0 && bRead > 0) {
        int c = Integer.compare(a[aRead - 1], b[bRead - 1]);
        while (aRead > 0 && bRead > 0) {
            switch (c) {
                default:
                    gallopPos = gallopSearch(aRead, a, b[bRead-1]);
                    length = (aRead - gallopPos);
                    write -= length;
                    aRead = gallopPos;
                    System.arraycopy(a, gallopPos--, results, write, length);
                    c = -1;
                    break;
                case -1:
                    gallopPos = gallopSearch(bRead, b, a[aRead-1]);
                    length = (bRead - gallopPos);
                    write -= length;
                    bRead = gallopPos;
                    System.arraycopy(b, gallopPos--, results, write, length);
                    c = 1;
                    break;
            }
        }
    }
    if (bRead > 0) {
        if (b != results) {
            System.arraycopy(b, 0, results, 0, bRead);
        }
    } else if (aRead > 0) {
        if (a != results) {
            System.arraycopy(a, 0, results, 0, aRead);
        }
    }
    return results;
}

Dies sollte der effizienteste Weg sein, dies zu tun.


Einige Antworten hatten eine doppelte Entfernungsfähigkeit. Dies erfordert einen O (n) -Algorithmus, da Sie tatsächlich jedes Element vergleichen müssen. Hier ist also eine eigenständige Anwendung, die nachträglich angewendet werden kann. Sie können nicht durch mehrere Einträge galoppieren, wenn Sie sich alle ansehen müssen, obwohl Sie durch die Duplikate galoppieren könnten, wenn Sie viele davon hätten.

static public int removeDuplicates(int[] list, int size) {
    int write = 1;
    for (int read = 1; read < size; read++) {
        if (list[read] == list[read - 1]) {
            continue;
        }
        list[write++] = list[read];
    }
    return write;
}

Update: Vorherige Antwort, kein schrecklicher Code, aber deutlich schlechter als oben.

Eine weitere unnötige Hyperoptimierung. Es ruft nicht nur Arraycopy für die Endbits auf, sondern auch für den Anfang. Verarbeiten einer einleitenden Nichtüberlappung in O (log (n)) durch eine binäre Suche in den Daten. O (log (n) + n) ist O (n) und in einigen Fällen ist der Effekt ziemlich ausgeprägt, insbesondere wenn es überhaupt keine Überlappung zwischen den zusammengeführten Arrays gibt.

private static int binarySearch(int[] array, int low, int high, int v) {
    high = high - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = array[mid];
        if (midVal > v)
            low = mid + 1;
        else if (midVal < v)
            high = mid - 1;
        else
            return mid; // key found
    }
    return low;//traditionally, -(low + 1);  // key not found.
}

private static int[] sortedArrayMerge(int a[], int b[]) {
    int result[] = new int[a.length + b.length];
    int k, i = 0, j = 0;
    if (a[0] > b[0]) {
        k = i = binarySearch(b, 0, b.length, a[0]);
        System.arraycopy(b, 0, result, 0, i);
    } else {
        k = j = binarySearch(a, 0, a.length, b[0]);
        System.arraycopy(a, 0, result, 0, j);
    }
    while (i < a.length && j < b.length) {
        result[k++] = (a[i] < b[j]) ? a[i++] : b[j++];
    }
    if (j < b.length) {
        System.arraycopy(b, j, result, k, (b.length - j));
    } else {
        System.arraycopy(a, i, result, k, (a.length - i));
    }
    return result;
}
Tatarisieren
quelle
1
Upvoted für den Beginn, etwas gegen die Symmetrie zu tun, aber warum dort aufhören? Verwenden Sie die galoppierende Suche und lassen Sie den Index nach gleichen Schlüsseln zurückgeben. Verwenden Sie die Array-Kopie nur für mehr als 3 Elemente. Beachten Sie, dass sich nach dieser Kopie nichts geändert hat, außer a) dem Startindex in einer Eingabe und dem Ausgabearray b) Ihrem Wissen darüber, welches "nächste" Element kleiner ist.
Graubart
Genau das macht die implementierte Arrays.sort. Es ist im schlimmsten Fall eine Zusammenführungssorte. Ich denke, sie tauschen bei Bedarf 2 Elemente aus, fallen aber für mehr als 2 Elemente in die Arraycopy. Ich bin mir nicht sicher, ob Sie linear oder binär nach dem nächsten Element suchen würden. Es wäre ein ziemlich großer Vorteil, spekulativ zu prüfen, ob Sie eine größere Distanz galoppieren könnten, wenn Sie diese Distanz galoppieren könnten. Wie Check 8 im Voraus, und wenn Sie kopieren können, dass Sie sich 7 Operationen von Dingen gespeichert haben, die Sie nicht betrachten müssen.
Tatarize
@ Greybeard ... und fertig. Ging auch rückwärts, damit ich den gleichen Speicher wiederverwenden konnte.
Tatarize
Gut, dass Sie motiviert haben, ballistisch zu werden. Ich werde mir die Zeitsenken am Tag genauer ansehen.
Graubart
That is totally what the implemented Arrays.sort does( Das : aus der ersten Überarbeitung Ihrer Antwort - oder - aus meinem Kommentar vom 19. Februar?) - kann auch in Sunsofts JDK 8 nicht gefunden werden: Auf welche Implementierung von Arrays.sortbeziehen Sie sich?
Graubart
2

Hier ist eine gekürzte Form in Javascript geschrieben:

function sort( a1, a2 ) {

    var i = 0
        , j = 0
        , l1 = a1.length
        , l2 = a2.length
        , a = [];

    while( i < l1 && j < l2 ) {

        a1[i] < a2[j] ? (a.push(a1[i]), i++) : (a.push( a2[j]), j++);
    }

    i < l1 && ( a = a.concat( a1.splice(i) ));
    j < l2 && ( a = a.concat( a2.splice(j) ));

    return a;
}
schlucken
quelle
1
    public class Merge {

    // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
    public static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

        // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid+1, hi);

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k]; 
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              a[k] = aux[j++];
            else if (j > hi)               a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else                           a[k] = aux[i++];
        }

        // postcondition: a[lo .. hi] is sorted
        assert isSorted(a, lo, hi);
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }

    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length-1);
        assert isSorted(a);
    }


   /***********************************************************************
    *  Helper sorting functions
    ***********************************************************************/

    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }

    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


   /***********************************************************************
    *  Check if array is sorted - useful for debugging
    ***********************************************************************/
    private static boolean isSorted(Comparable[] a) {
        return isSorted(a, 0, a.length - 1);
    }

    private static boolean isSorted(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i-1])) return false;
        return true;
    }


   /***********************************************************************
    *  Index mergesort
    ***********************************************************************/
    // stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
    private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = index[k]; 
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)                    index[k] = aux[j++];
            else if (j > hi)                     index[k] = aux[i++];
            else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
            else                                 index[k] = aux[i++];
        }
    }

    // return a permutation that gives the elements in a[] in ascending order
    // do not change the original array a[]
    public static int[] indexSort(Comparable[] a) {
        int N = a.length;
        int[] index = new int[N];
        for (int i = 0; i < N; i++)
            index[i] = i;

        int[] aux = new int[N];
        sort(a, index, aux, 0, N-1);
        return index;
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, index, aux, lo, mid);
        sort(a, index, aux, mid + 1, hi);
        merge(a, index, aux, lo, mid, hi);
    }

    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    // Read strings from standard input, sort them, and print.
    public static void main(String[] args) {
        String[] a = StdIn.readStrings();
        Merge.sort(a);
        show(a);
    }
}
Jackhao
quelle
Was kopiert diese a[mid+1 .. hi]auf auxfür?
Graubart
1

Ich denke, die Einführung der Überspringliste für das größere sortierte Array kann die Anzahl der Vergleiche verringern und den Kopiervorgang in das dritte Array beschleunigen. Dies kann gut sein, wenn das Array zu groß ist.

Sriragav
quelle
1
public int[] merge(int[] a, int[] b) {
    int[] result = new int[a.length + b.length];
    int aIndex, bIndex = 0;

    for (int i = 0; i < result.length; i++) {
        if (aIndex < a.length && bIndex < b.length) {
            if (a[aIndex] < b[bIndex]) {
                result[i] = a[aIndex];
                aIndex++;
            } else {
                result[i] = b[bIndex];
                bIndex++;
            }
        } else if (aIndex < a.length) {
            result[i] = a[aIndex];
            aIndex++;
        } else {
            result[i] = b[bIndex];
            bIndex++;
        }
    }

    return result;
}
Andrew
quelle
2
Eine Erklärung wäre schön. :)
gsamaras
1
public static int[] merge(int[] a, int[] b) {
    int[] mergedArray = new int[(a.length + b.length)];
    int i = 0, j = 0;
    int mergedArrayIndex = 0;
    for (; i < a.length || j < b.length;) {
        if (i < a.length && j < b.length) {
            if (a[i] < b[j]) {
                mergedArray[mergedArrayIndex] = a[i];
                i++;
            } else {
                mergedArray[mergedArrayIndex] = b[j];
                j++;
            }
        } else if (i < a.length) {
            mergedArray[mergedArrayIndex] = a[i];
            i++;
        } else if (j < b.length) {
            mergedArray[mergedArrayIndex] = b[j];
            j++;
        }
        mergedArrayIndex++;
    }
    return mergedArray;
}
toobsco42
quelle
Was ist die rettende Gnade davon? Es kann geschrumpft werden for (int i, j, k = i = j = 0 ; k < c.length ; ) c[k++] = b.length <= j || i < a.length && a[i] < b[j] ? a[i++] : b[j++];. Wie unterscheidet es sich von Andrews Antwort von 2014 ?
Graubart
1

Der Algorithmus könnte auf viele Arten verbessert werden. Zum Beispiel ist es sinnvoll zu prüfen, ob a[m-1]<b[0]oder b[n-1]<a[0]. In keinem dieser Fälle müssen weitere Vergleiche durchgeführt werden. Der Algorithmus könnte einfach Quell-Arrays in der resultierenden Reihenfolge in der richtigen Reihenfolge kopieren.

Kompliziertere Verbesserungen können das Suchen nach verschachtelten Teilen und das Ausführen eines Zusammenführungsalgorithmus nur für diese umfassen. Dies kann viel Zeit sparen, wenn sich die Größen der zusammengeführten Arrays mehrmals unterscheiden.

Hengameh
quelle
Für diese Verbesserung ist es besser, mit einer Binärsuche zu überprüfen, wo das erste Element in das zweite Array fällt, und dann diese Daten zu Beginn zu kopieren. In dem Fall, dass eine dieser Prüfungen wahr ist, würde nur Arraycopy alles und dann Arraycopy das Ternäre haben und Sie erhalten das gleiche Ergebnis. Im Falle einer winzigen Überlappung müssen Sie jedoch nur während der Überlappung und zu keinem anderen Zeitpunkt den richtigen Algorithmus ausführen. Da Sie mit O (n) nicht weiterkommen, wird es nichts kosten, wenn Sie vorher einen schnellen O (logn) -Befehl verwenden.
Tatarize
1

Dieses Problem hängt mit dem Mergesort-Algorithmus zusammen, bei dem zwei sortierte Unterarrays zu einem einzigen sortierten Unterarray kombiniert werden. Das CLRS- Buch enthält ein Beispiel für den Algorithmus und beseitigt die Notwendigkeit, zu überprüfen, ob das Ende erreicht wurde, indem am Ende jedes Arrays ein Sentinel-Wert (etwas, das vergleichbar und "größer als jeder andere Wert" ist) hinzugefügt wird.

Ich habe dies in Python geschrieben, aber es sollte sich auch gut in Java übersetzen lassen:

def func(a, b):
    class sentinel(object):
        def __lt__(*_):
            return False

    ax, bx, c = a[:] + [sentinel()], b[:] + [sentinel()], []
    i, j = 0, 0

    for k in range(len(a) + len(b)):
        if ax[i] < bx[j]:
            c.append(ax[i])
            i += 1
        else:
            c.append(bx[j])
            j += 1

    return c
d11wtq
quelle
Massenkopieren
1

Sie können 2 Threads verwenden, um das resultierende Array zu füllen, einen von vorne und einen von hinten.

Dies kann bei Zahlen ohne Synchronisation funktionieren, z. B. wenn jeder Thread die Hälfte der Werte einfügt.

tkruse
quelle
0
//How to merge two sorted arrays into a sorted array without duplicates?
//simple C Coding
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

main()
{
    int InputArray1[] ={1,4,5,7,8,9,12,13,14,17,40};
    int InputArray2[] ={4,5,11,14,15,17,18,19,112,122,122,122,122};
    int n=10;
    int OutputArray[30];
    int i=0,j=0,k=0;
    //k=OutputArray
    while(i<11 && j<13)
    {
        if(InputArray1[i]<InputArray2[j])
        {
            if (k == 0 || InputArray1[i]!= OutputArray[k-1])
            {
                OutputArray[k++] = InputArray1[i];
            }
            i=i+1;
        }
        else if(InputArray1[i]>InputArray2[j])
        {
            if (k == 0 || InputArray2[j]!= OutputArray[k-1])
            {
                OutputArray[k++] = InputArray2[j];
            }
            j=j+1;
        }
        else
        {
            if (k == 0 || InputArray1[i]!= OutputArray[k-1])
            {
                OutputArray[k++] = InputArray1[i];
            }
            i=i+1;
            j=j+1;
        }
    };
    while(i<11)
    {
        if(InputArray1[i]!= OutputArray[k-1])
            OutputArray[k++] = InputArray1[i++];
        else
            i++;
    }
    while(j<13)
    {
        if(InputArray2[j]!= OutputArray[k-1])
            OutputArray[k++] = InputArray2[j++];
        else
            j++;
    }
    for(i=0; i<k; i++)
    {
        printf("sorted data:%d\n",OutputArray[i]);
    };
}
Chanchal
quelle
0
public static int[] merge(int[] listA, int[] listB) {
        int[] mergedList = new int[ listA.length + listB.length];
        int i = 0; // Counter for listA
        int j = 0; // Counter for listB
        int k = 0; // Counter for mergedList
        while (true) {
            if (i >= listA.length && j >= listB.length) {
                break;
            }
            if (i < listA.length && j < listB.length) { // If both counters are valid.
                if (listA[i] <= listB[j]) {
                    mergedList[k] = listA[i];
                    k++;
                    i++;
                } else {
                    mergedList[k] = listB[j];
                    k++;
                    j++;
                }
            } else if (i < listA.length && j >= listB.length) { // If only A's counter is valid.
                mergedList[k] = listA[i];
                k++;
                i++;
            } else if (i <= listA.length && j < listB.length) { // If only B's counter is valid
                mergedList[k] = listB[j];
                k++;
                j++;
            }
        }
        return mergedList;
    }
Sean Woolfolk
quelle
0
var arrCombo = function(arr1, arr2){
  return arr1.concat(arr2).sort(function(x, y) {
    return x - y;
  });
};
Alex Hawkins
quelle
2
Diese Antwort gilt nicht für die Programmiersprache Java, obwohl sie eine gute Antwort für Javascript wäre.
Gknicker
Dies war Teil eines Vorstellungsgesprächs. In diesen Fällen wird nicht wirklich erwartet, dass Sie "normalen" Code wie oben schreiben. Sie suchen nach "effizientem" Code und einer Demonstration, dass Sie die beteiligten Algorithmen verstehen.
d11wtq
0

Meine Lieblingsprogrammiersprache ist JavaScript

function mergeSortedArrays(a, b){
    var result = [];

    var sI = 0;
    var lI = 0;
    var smallArr;
    var largeArr;
    var temp;

    if(typeof b[0] === 'undefined' || a[0]<b[0]){
        smallArr = a;
        largeArr = b;
    } else{
        smallArr = b;
        largeArr = a;
    }

    while(typeof smallArr[sI] !== 'undefined'){
        result.push(smallArr[sI]);
        sI++;

        if(smallArr[sI]>largeArr[lI] || typeof smallArr[sI] === 'undefined'){
            temp = smallArr;
            smallArr = largeArr;
            largeArr = temp;
            temp = sI;
            sI = lI;
            lI = temp;
        }
    }
    return result;
}
Saad Ahmed
quelle
0

Verwenden Sie möglicherweise System.arraycopy

public static byte[] merge(byte[] first, byte[] second){
    int len = first.length + second.length;
    byte[] full = new byte[len];
    System.arraycopy(first, 0, full, 0, first.length);
    System.arraycopy(second, 0, full, first.length, second.length);
    return full;
}
nurisezgin
quelle
3
Sie verschmelzen sie nur; Ihr resultierendes Array selbst ist nicht sortiert, was eine Anforderung war.
Sanjeev Dhiman
0
public static void main(String[] args) {
    int[] arr1 = {2,4,6,8,10,999};
    int[] arr2 = {1,3,5,9,100,1001};

    int[] arr3 = new int[arr1.length + arr2.length];

    int temp = 0;

    for (int i = 0; i < (arr3.length); i++) {
        if(temp == arr2.length){
            arr3[i] = arr1[i-temp];
        }
        else if (((i-temp)<(arr1.length)) && (arr1[i-temp] < arr2[temp])){
                arr3[i] = arr1[i-temp];
        }
        else{
            arr3[i] = arr2[temp];
            temp++;
        }
    }

    for (int i : arr3) {
        System.out.print(i + ", ");
    }
}

Ausgabe ist:

1, 2, 3, 4, 5, 6, 8, 9, 10, 100, 999, 1001,

Rajesh Gurbani
quelle
Verwirrend für die Benennung des Index in arr2nicht ind2, aber temp.
Graubart
0

Sie können ternäre Operatoren verwenden, um den Code etwas kompakter zu gestalten

public static int[] mergeArrays(int[] a1, int[] a2) {
    int[] res = new int[a1.length + a2.length];
    int i = 0, j = 0;

    while (i < a1.length && j < a2.length) {
        res[i + j] = a1[i] < a2[j] ? a1[i++] : a2[j++];
    }

    while (i < a1.length) {
        res[i + j] = a1[i++];
    }

    while (j < a2.length) {
        res[i + j] = a2[j++];
    }

    return res;
}
Jenna Kwon
quelle
0
public static int[] mergeSorted(int[] left, int[] right) {
    System.out.println("merging " + Arrays.toString(left) + " and " + Arrays.toString(right));
    int[] merged = new int[left.length + right.length];
    int nextIndexLeft = 0;
    int nextIndexRight = 0;
    for (int i = 0; i < merged.length; i++) {
        if (nextIndexLeft >= left.length) {
            System.arraycopy(right, nextIndexRight, merged, i, right.length - nextIndexRight);
            break;
        }
        if (nextIndexRight >= right.length) {
            System.arraycopy(left, nextIndexLeft, merged, i, left.length - nextIndexLeft);
            break;
        }
        if (left[nextIndexLeft] <= right[nextIndexRight]) {
            merged[i] = left[nextIndexLeft];
            nextIndexLeft++;
            continue;
        }
        if (left[nextIndexLeft] > right[nextIndexRight]) {
            merged[i] = right[nextIndexRight];
            nextIndexRight++;
            continue;
        }
    }
    System.out.println("merged : " + Arrays.toString(merged));
    return merged;
}

Nur ein kleiner Unterschied zur ursprünglichen Lösung

Ranga
quelle
0

Um zwei sortierte Arrays in der O (m + n) -Zeitkomplexität zusammenzufassen, verwenden Sie den folgenden Ansatz mit nur einer Schleife. m und n ist die Länge des ersten Arrays und des zweiten Arrays.

public class MargeSortedArray {
    public static void main(String[] args) {
        int[] array = new int[]{1,3,4,7};
        int[] array2 = new int[]{2,5,6,8,12,45};
        int[] newarry = margeToSortedArray(array, array2);
        //newarray is marged array
    }

    // marge two sorted array with o(a+n) time complexity
    public static int[] margeToSortedArray(int[] array, int[] array2) {
        int newarrlen = array.length+array2.length;
        int[] newarr = new int[newarrlen];

        int pos1=0,pos2=0;
        int len1=array.length, len2=array2.length;

        for(int i =0;i<newarrlen;i++) {     
            if(pos1>=len1) {
                newarr[i]=array2[pos2];
                pos2++;
                continue;
            }
            if(pos2>=len2) {
                newarr[i]=array[pos1];
                pos1++;
                continue;
            }

            if(array[pos1]>array2[pos2]) {
                newarr[i]=array2[pos2];
                pos2++;
            } else {
                newarr[i]=array[pos1];
                pos1++;
            }   
        }

        return newarr;
    }

}
Birbal Singh
quelle
0
var arr1 = [2,10,20,30,100];
var arr2 = [2,4,5,6,7,8,9];
var j = 0;
var i =0;
var newArray = [];

for(var x=0;x< (arr1.length + arr2.length);x++){
    if(arr1[i] >= arr2[j]){                //check if element arr2 is equal and less than arr1 element
        newArray.push(arr2[j]);
      j++;
    }else if(arr1[i] < arr2[j]){            //check if element arr1 index value  is less than arr2 element
        newArray.push(arr1[i]);
        i++;
    }
    else if(i == arr1.length || j < arr2.length){    // add remaining arr2 element
        newArray.push(arr2[j]);
        j++
    }else{                                                   // add remaining arr1 element
        newArray.push(arr1[i]); 
        i++
    }

}

console.log(newArray);
Amar1990
quelle
-1

Da die Frage keine bestimmte Sprache annimmt. Hier ist die Lösung in Python. Angenommen, die Arrays sind bereits sortiert.

Ansatz 1 - Verwenden von Numpy-Arrays: Importieren Sie Numpy

arr1 = numpy.asarray([ 1,  2,  3,  4,  5,  6,  7,  8,  9, 11, 14, 15, 55])
arr2 = numpy.asarray([11, 32, 43, 45, 66, 76, 88])

array = numpy.concatenate((arr1,arr2), axis=0)
array.sort()

Ansatz 2 - Verwenden der Liste unter der Annahme, dass die Listen sortiert sind.

list_new = list1.extend(list2)
list_new.sort()
Rahul Biswas
quelle
Since the question doesn't assume any specific languagevom 2011/5/11/19: 43 ist es mit Java getaggt .
Graubart
Ihre Lösung nicht den Vorteil der Tatsache , Listen nehmen bereits sortiert, und die Laufzeit ist nicht O (n), da .sort()ist O(n log n)bestenfalls
dark_ruby
-1

Hier ist meine Java-Implementierung, die Duplikate entfernt.

public static int[] mergesort(int[] a, int[] b) {
    int[] c = new int[a.length + b.length];
    int i = 0, j = 0, k = 0, duplicateCount = 0;

    while (i < a.length || j < b.length) {
        if (i < a.length && j < b.length) {
            if (a[i] == b[j]) {
                c[k] = a[i];
                i++;j++;duplicateCount++;
            } else {
                c[k] = a[i] < b[j] ? a[i++] : b[j++];
            }
        } else if (i < a.length) {
            c[k] = a[i++];
        } else if (j < a.length) {
            c[k] = b[j++];
        }
        k++;
    }

    return Arrays.copyOf(c, c.length - duplicateCount);
}
kdebugging
quelle