Arrays vergleichen

Ü

überlebender

Aktives Mitglied
Ich möchte folgende Methode schreiben:

Modifikatoren: public und static
Rückgabetyp: boolean
Methodenname: compareArrays
Übergabeparameter: int-Array a, int-Array b

Die Methode compareArrays gibt genau dann den Wert true zurück, wenn die Werte, die in a und in b enthalten sind, gleich sind und gleich oft vorkommen und in der gleichen Reihenfolge in den jeweiligen Arrays enthalten sind.


Beispiel: Es sei a={1,2,3}, b = {1,2,4}, c={1,3,2}, d={1,2} und e={1,2,3}. Dann ist der Rückgabewert von compareArrays false, mit Ausnahme von compareArrays(a,e) bzw. compareArrays(e,a) bzw. Aufrufen, in denen das gleiche Array zweimal als Übergabeparameter eingegeben wird.

Mein Versuch:

Ich habe Stift und Papier genommen, meine Ideen aufgeschrieben und versucht, diese in einen Code umzuwandeln. Ich bin blutiger Anfänger am Anfang des Informatik Studiums, also seid bitte gnädig.
Java: 
package a4;

public class A4_main {

    public static boolean compareArrays(int [] a, int [] b) {
      
        for (int i=0; i < a.length && i < b.length; i++) {
          
            if (a[i] != b[i]) && (if a.length[i] != b.length[i]);
          
            return false;
            }
            return true;
            }
}


Hab hier nur geschafft, die Kriterien "gleich" und "gleich oft" zu schreiben.
Bei "gleiche Reihenfolge" habe ich keine Idee.
 
Zuerst würde ich prüfen ob die Arrays auch die gleiche Länge haben. Ist das nicht der Fall ist der Test schon zu Ende. Danach kann man in einer Schleife die Elemente vergleichen.
 
if (a[i] != b[i]) && (if a.length[i] != b.length[i]); Das ";" am Ende ist sowas wie ein leeres Statement. Die if Anweisung ist da also komplett zu Ende. Damit wird immer ein return false ausgeführt!

Wenn Du das Semikolon weg löschst, dann dürfte es schon (fast) funktionieren. Der Hinweis von @Oneixee5 ist aber wichtig bezüglich der Größe der Arrays. Bei den Beispielen wird der Code - so du ihn wie vorgeschlagen korrigierst - wohl funktionieren. Aber teste einmal die Vergleiche mit einem der Array mit einem leeren Array! Was passiert dann? Weil das leere Array keine Elemente hat geht er nicht in die Schleife und somit kommt er nie zu dem Check der Längen und es wird dann true zurück gegeben.
 
Den Punkt hatte ich noch übersehen, da ich mich auf den Code konzentriert habe:
überlebender hat gesagt.:
Hab hier nur geschafft, die Kriterien "gleich" und "gleich oft" zu schreiben.
Bei "gleiche Reihenfolge" habe ich keine Idee.
Zum Vergrößern anklicken....
Was bedeutet denn gleiche Reihenfolge der Werte im Array?

1, 2, 3 und 3, 2, 1 hätten jeweils die gleichen Werte aber nicht die gleiche Reihenfolge.

Unter dem Strich bedeutet das doch, dass die Werte an einer Position i bei beiden Array den gleichen Wert haben müssen. Und das prüfst Du ja in deiner Bedingung ab: Wenn an Position i die Werte von Array a und Array b ungleich sind, dann sind die Array nicht gleich.
 
KonradN hat gesagt.:
Den Punkt hatte ich noch übersehen, da ich mich auf den Code konzentriert habe:

Was bedeutet denn gleiche Reihenfolge der Werte im Array?

1, 2, 3 und 3, 2, 1 hätten jeweils die gleichen Werte aber nicht die gleiche Reihenfolge.

Unter dem Strich bedeutet das doch, dass die Werte an einer Position i bei beiden Array den gleichen Wert haben müssen. Und das prüfst Du ja in deiner Bedingung ab: Wenn an Position i die Werte von Array a und Array b ungleich sind, dann sind die Array nicht gleich.
Zum Vergrößern anklicken....
So hab da jetzt einen Lösungsansatz gefunden, weiß aber nicht ob das so klappt.
Java: 
package a4;

public class A4_main {

    public static boolean compareArrays(int [] a, int [] b) {
      
        if (a.length != b.length) {
            return false;                  // gleiche Anzahl an Werten
        }
      
        for (int i=0; i < a.length; i++) {
          
            if (a[i] != b[i]) {           // gleiche Werte
          
            return false; }
      
        for (int x=0; x < a.length || x < b.length; x++) {
          
            if (a[0] != b[0]);           // gleiche Reihenfolge (hier bin ich mir nicht sicher ob das klappt)
            return false;
        }
          
          
            }
            return true;
            }
  
public stativ void main (String [] args) {
    System.print.out()   //?
}

*In Zeile 19 möchte ich prüfen, ob beide Arrays die gleiche Reihenfolge haben.
Meine Idee war, dass wenn array a Index 0,1,2,3 den gleichen Wert hat wie array b Index 0,1,2,3 usw., dann soll true rauskommen, andernfalls false
 
überlebender hat gesagt.:
Java: 
if (a[i] != b[i]) && (if a.length[i] != b.length[i]);
Zum Vergrößern anklicken....
Den Punkt bzgl. des Semikolons hat @KonradN ja schon angesprochen, wenn wir das mal etwas anders formatieren, sieht es so aus:
Java: 
if (a[i] != b[i]) && (if a.length[i] != b.length[i])
    ;
Dabei ist aber noch wichtig, dass die if-Anweisung in der Form syntaktisch falsch ist. Die Syntax lautet
Java: 
if ( Ausdruck )
Im Ausdruck selbst kommt kein if vor und der Ausdruck muss geklammert werden, das ist bei Dir nicht der Fall.

Wenn wir das if im Ausdruck entfernen, lautet er (a[i] != b[i]) && (a.length[i] != b.length[i]). Im if-Statement sieht das also so aus:
Java: 
if ( (a[i] != b[i]) && (a.length[i] != b.length[i]) )

Natürlich sind auch a.length[i] und b.length[i] noch falsch. a und b sind Arrays und die haben eine Länge: a.length != b.length. Damit ist auch klar, dass sich die Länge nicht auf ein einzelnes Element bezieht, so dass die Prüfung hier nicht besonders sinnvoll ist.
 
überlebender hat gesagt.:
So hab da jetzt einen Lösungsansatz gefunden, weiß aber nicht ob das so klappt.
Zum Vergrößern anklicken....
Fast, wenn Du den Code richtig formatierst, ein paar Fehler rausmachst und die überflüssige Schleife in 17 - 20:
Java: 
    public static boolean compareArrays(int [] a, int [] b) {
        
        if (a.length != b.length) {
            return false;                  // gleiche Anzahl an Werten
        }
        
        for (int i=0; i < a.length; i++) {            
            if (a[i] != b[i]) {           // gleiche Werte UND gleiche Reihenfolge!
                return false;
            }
        }

        // kommt man während der Ausführung bis zu diesem Punkt,
        // haben alle Elemente den gleichen Wert und zwar in der gleichen Reihenfolge.

        return true;
    }
    
    public static void main (String [] args) {
        int[] a = {1,2,3,4,5};
        int[] b = {1,2,3,4,6};
        System.out.println(compareArrays(a, a));
        System.out.println(compareArrays(a, b));
    }
 
mihe7 hat gesagt.:
Den Punkt bzgl. des Semikolons hat @KonradN ja schon angesprochen, wenn wir das mal etwas anders formatieren, sieht es so aus:
Java: 
if (a[i] != b[i]) && (if a.length[i] != b.length[i])
    ;
Dabei ist aber noch wichtig, dass die if-Anweisung in der Form syntaktisch falsch ist. Die Syntax lautet
Java: 
if ( Ausdruck )
Im Ausdruck selbst kommt kein if vor und der Ausdruck muss geklammert werden, das ist bei Dir nicht der Fall.

Wenn wir das if im Ausdruck entfernen, lautet er (a[i] != b[i]) && (a.length[i] != b.length[i]). Im if-Statement sieht das also so aus:
Java: 
if ( (a[i] != b[i]) && (a.length[i] != b.length[i]) )

Natürlich sind auch a.length[i] und b.length[i] noch falsch. a und b sind Arrays und die haben eine Länge: a.length != b.length. Damit ist auch klar, dass sich die Länge nicht auf ein einzelnes Element bezieht, so dass die Prüfung hier nicht besonders sinnvoll ist.
Zum Vergrößern anklicken....
 
mihe7 hat gesagt.:
Fast, wenn Du den Code richtig formatierst, ein paar Fehler rausmachst und die überflüssige Schleife in 17 - 20:
Java: 
    public static boolean compareArrays(int [] a, int [] b) {
     
        if (a.length != b.length) {
            return false;                  // gleiche Anzahl an Werten
        }
     
        for (int i=0; i < a.length; i++) {         
          if a[i] != b[i] {           // gleiche Werte UND gleiche Reihenfolge!
                return false;
            }
        }

        // kommt man während der Ausführung bis zu diesem Punkt,
        // haben alle Elemente den gleichen Wert und zwar in der gleichen Reihenfolge.

        return true;
    }
 
    public static void main (String [] args) {
        int[] a = {1,2,3,4,5};
        int[] b = {1,2,3,4,6};
        System.out.println(compareArrays(a, a));
        System.out.println(compareArrays(a, b));
    }
Zum Vergrößern anklicken....
Was ist wenn die Reihenfolge egal wäre, aber die Werte trotzdem gleich oft vorkommen und gleich sein sollen?

Könnte ich die for-Schleife weglassen und nur die Bedingung
Code: 
  if a[i] != b[i]
in die erste if-Anweisung einfügen, also:
Code: 
 if (a.length != b.length && a[i] != b[i]) {    // gleiche Anzahl an Werten und gleiche Werte

            return false;               

        }
 
mihe7 hat gesagt.:
Da Du an der Stelle den Index i nicht zur Verfügung hast, funktioniert das nicht.


Dann brauchst Du eine andere Strategie. Kannst Du Dir ja mal überlegen (Zettel!)
Zum Vergrößern anklicken....
Ja das ist einleuchtend.

Nach so einigen Überlegungen bin ich auf die Idee gekommen, dass wenn die Werte identisch sind, dann ist doch automatisch auch die Anzahl der Werte identisch.

Es scheint irgendwie zu einfach um wahr zu sein, geht auch nicht.
Wenn array a kleiner ist als b, dann kommt trotzdem true raus
 
KonradN hat gesagt.:
Wenn Du in #7 schaust, dann siehst Du doch den Check, der dafür mit im Code ist:
Java: 
        if (a.length != b.length) {
            return false;                  // gleiche Anzahl an Werten
        }

Diesen Check brauchst Du natürlich und den darfst Du nicht weglassen.
Zum Vergrößern anklicken....
Java: 
if (a[i] != b[i]) {

Dieser Check prüft, ob beide arrays gleiche Reihenfolge und gleiche Werte haben.

Wenn die Reihenfolge egal sein soll, dann muss bei
a = {1,2,3,4} und
b = {2,1,4,3}
auch true rauskommen, weil gleiche Länge und gleiche Werte
 
Bei so Aufgaben immer überlegen: Wie machst Du es? Wenn du zwei Zahlenreihen bekommst und feststellen sollst, ob die Zahlen prinzipiell gleich sind und nur die Reihenfolge unterschiedlich ist?

Das ist generell der Ansatz, der immer gegangen wird. Daher: Wie gehst Du vor?
Du wirst doch bestimmt irgendwelche Ideen haben, wie Du sowas heraus finden kannst...
 
KonradN hat gesagt.:
Bei so Aufgaben immer überlegen: Wie machst Du es? Wenn du zwei Zahlenreihen bekommst und feststellen sollst, ob die Zahlen prinzipiell gleich sind und nur die Reihenfolge unterschiedlich ist?

Das ist generell der Ansatz, der immer gegangen wird. Daher: Wie gehst Du vor?
Du wirst doch bestimmt irgendwelche Ideen haben, wie Du sowas heraus finden kannst...
Zum Vergrößern anklicken....
Ja ich habe tatsächlich eine Idee:

z.B.
1. Kartesisches Produkt bilden
2. vergleichen welche paare identisch sind

also int [] a x int [] b
if Wertepaar 1 (a[0] = b[0])
return true

Vom Grundgedanken her muss man ja alle Indexe von array a mit allen indexen von array b vergleichen.
Das Programm muss auf dem Weg einen identischen Wert finden.
d.h. wir vergleichen zuerst a[0] mit b [0-b.length], danach a[1] mit b[0- b.length] usw.
 
überlebender hat gesagt.:
Ja ich habe tatsächlich eine Idee:

z.B.
1. Kartesisches Produkt bilden
2. vergleichen welche paare identisch sind

also int [] a x int [] b
if Wertepaar 1 (a[0] = b[0])
return true

Vom Grundgedanken her muss man ja alle Indexe von array a mit allen indexen von array b vergleichen.
Das Programm muss auf dem Weg einen identischen Wert finden.
d.h. wir vergleichen zuerst a[0] mit b [0-b.length], danach a[1] mit b[0- b.length] usw.
Zum Vergrößern anklicken....
Da sehe ich aber erst einmal nicht, wie Du da zu einem Ergebnis kommst, das Du haben willst.

Daher noch einmal: Was machst Du, wenn ich Dich bitte, die Listen 1, 1, 2, 2 und 2, 2, 1, 1 bezüglich der Anzahl der Elemente zu vergleichen?

Bildest Du da wirklich das Kartesische Produkt? Also
1, 2
1, 2
1, 1
1, 1
1, 2
1, 2
1, 1
1, 1
2, 2
2, 2
2, 1
2, 1
2, 2
2, 2
2, 1
2, 1

Und da kommt dann raus: 8 gleiche Paare... Wie hilft Dir das?

1, 1, 1, 2 und 2, 1, 1, 1 könnte man ja auch mal nehmen ... ich schreibe es jetzt nicht auf, aber da gibt es dann 10 gleiche Paare...
 
mihe7 hat gesagt.:
Hier kommt wieder der Zettel ins Spiel: schreib Dir zwei beliebige "Arrays" auf und versuch das Problem auf dem Zettel zu lösen. Als Hinweis kann ich Dir noch mitgeben, dass sich dieses Problem nicht ganz so einfach lösen lässt, wie das vorherige.
Zum Vergrößern anklicken....
Eigentlich muss es recht simpel sein, denn im 1.Semester habe ich noch nicht genug Wissen um so richtig komplexe sachen zu basteln.

Außer arrays, schleifen, if, else-if und Methoden und die 8 primitiven Datentypen haben wir noch nicht viel gemacht.
 
Also noch einmal ganz deutlich: Vergiss die Software Entwicklung. Es gibt ein fachliches Problem und das sollst Du in Gedanken lösen. Da geht es um ein Verfahren!

Evtl. um es etwas bildlicher zu machen:

Du bekommst zwei Stapel Geldscheine. Und nun ist die Frage: Sind in beiden Stapeln genau die gleichen Geldscheine?

Kriegst Du das irgendwie hin? Wenn ja: Wie gehst Du dazu vor?
 
KonradN hat gesagt.:
Da sehe ich aber erst einmal nicht, wie Du da zu einem Ergebnis kommst, das Du haben willst.

Daher noch einmal: Was machst Du, wenn ich Dich bitte, die Listen 1, 1, 2, 2 und 2, 2, 1, 1 bezüglich der Anzahl der Elemente zu vergleichen?

Bildest Du da wirklich das Kartesische Produkt? Also
1, 2
1, 2
1, 1
1, 1
1, 2
1, 2
1, 1
1, 1
2, 2
2, 2
2, 1
2, 1
2, 2
2, 2
2, 1
2, 1

Und da kommt dann raus: 8 gleiche Paare... Wie hilft Dir das?

1, 1, 1, 2 und 2, 1, 1, 1 könnte man ja auch mal nehmen ... ich schreibe es jetzt nicht auf, aber da gibt es dann 10 gleiche Paare...
Zum Vergrößern anklicken....
Mein Gedanke wäre jetzt, wenn alle Zahlen in beiden Arrays n-mal vorkommen -> true
Wenn eine Zahl in einem array k-mal vorkommt und im anderen x-mal -> false

Also in etwa: if a = n && b= n -> true
Ich weiß nicht wie ich diesen Grundgedanken in Code ausdrücke.


Brauche ich dann 4 for-Schleifen?
jeweils für beide n's
und dann noch 2 für beide arrays?
 
KonradN hat gesagt.:
Also noch einmal ganz deutlich: Vergiss die Software Entwicklung. Es gibt ein fachliches Problem und das sollst Du in Gedanken lösen. Da geht es um ein Verfahren!

Evtl. um es etwas bildlicher zu machen:

Du bekommst zwei Stapel Geldscheine. Und nun ist die Frage: Sind in beiden Stapeln genau die gleichen Geldscheine?

Kriegst Du das irgendwie hin? Wenn ja: Wie gehst Du dazu vor?
Zum Vergrößern anklicken....
Ich zähle erst die Anzahl der 5€-Scheine, dann die Anzahl der 10€-Scheine usw.
Wenn die Anzahl aller verschiedenen Scheine gleich ist, dann sind in beiden Stapeln die gleichen Scheine.
 
mihe7 hat gesagt.:
Erstmal gar nicht. Löse das Geldscheinproblem
Zum Vergrößern anklicken....
Wir nehmen an:

1.Stapel......................2. Stapel
-1x 10€...................... -4x20€
-2x 50€.......................-2x50€
-4x20€........................-1x10€

Ich nehme den ersten Stapel, zähle alles durch und schreibe die Anzahl der 10, 20 und 50€ Scheine raus.
Danach nehme ich den zweiten Stapel, zähle alles durch und schreibe mir die Anzahl der 10, 20, 50€ Scheine raus.

Danach vergleiche ich beide Notizen. Selbe Anzahl, gleicher Schein? -> Ja
Falls im 1. Stapel zusätzlich noch ein 100€ Schein ist. Selbe Anzahl, gleicher Schein? -> Nein
 
überlebender hat gesagt.:
Ich zähle erst die Anzahl der 5€-Scheine, dann die Anzahl der 10€-Scheine usw.
Zum Vergrößern anklicken....
Ja, das wäre eine Möglichkeit. Der Ansatz setzt allerdings voraus, dass Du die Werte der Geldscheine bereits im Vorfeld kennst (was hier nicht der Fall ist). Ansonsten müsstest Du 4,2 Mrd. verschiedene Werte (32 Bit) durchzählen - da ist der Ansatz "etwas" aufwendig. Bekommst Du es ein klein wenig anders hin?
 
mihe7 hat gesagt.:
Der Ansatz setzt allerdings voraus, dass Du die Werte der Geldscheine bereits im Vorfeld kennst
Zum Vergrößern anklicken....
Das ist nicht zwingend notwendig. Wenn ich einen Stapel Geldscheine bekomme, dann zähle ich keine 5er, wenn es keine 5er gibt.

Da könnte man also überlegen, was für Zahlen man zählt.

Aber evtl. überlegt man einfach, wie man die Geldscheine zählt. Gehst du den Stapel mit allen Geldscheinen durch, um z.B. die 10er zu zählen?
 
mihe7 hat gesagt.:
Ja, das wäre eine Möglichkeit. Der Ansatz setzt allerdings voraus, dass Du die Werte der Geldscheine bereits im Vorfeld kennst (was hier nicht der Fall ist). Ansonsten müsstest Du 4,2 Mrd. verschiedene Werte (32 Bit) durchzählen - da ist der Ansatz "etwas" aufwendig. Bekommst Du es ein klein wenig anders hin?
Zum Vergrößern anklicken....
Vielleicht bilde ich die Summe?
Ich mein irgendwie muss das Programm doch durch die Werte gehen. Und wenn es 5 Milliarden sind, dann schafft das Programm das bestimmt auch nach längerer Zeit. Im Code implementiert man halt die Anweisung, es soll so lange durchgehen, wie das Array lang ist.
 
KonradN hat gesagt.:
Das ist nicht zwingend notwendig. Wenn ich einen Stapel Geldscheine bekomme, dann zähle ich keine 5er, wenn es keine 5er gibt.

Da könnte man also überlegen, was für Zahlen man zählt.

Aber evtl. überlegt man einfach, wie man die Geldscheine zählt. Gehst du den Stapel mit allen Geldscheinen durch, um z.B. die 10er zu zählen?
Zum Vergrößern anklicken....
Ich sortiere erst die Stapel und vergleiche danach.
 
mihe7 hat gesagt.:
Ja, das wäre eine Möglichkeit. Der Ansatz setzt allerdings voraus, dass Du die Werte der Geldscheine bereits im Vorfeld kennst (was hier nicht der Fall ist). Ansonsten müsstest Du 4,2 Mrd. verschiedene Werte (32 Bit) durchzählen - da ist der Ansatz "etwas" aufwendig. Bekommst Du es ein klein wenig anders hin?
Zum Vergrößern anklicken....
Ich glaub ich habs jetzt endlich. Ich glaub es kaum.
Also wenn man das Array zuerst sortiert, dann flieg ich vom Hocker.
 
Alternative könnte sein:
Ich gehe das erste Array Zahl für Zahl durch und zähle dann die Anzahl der Vorkommen.

Da zähle ich eine Zahl aber mehrfach - bei jedem Vorkommen.

Bei Deiner Beschreibung hattest Du etwas geschrieben, das ich so verstanden hatte, dass Du Ergebnisse aufschreibst. Das wäre dann also einfach, dass Du gezählte Zahlen merkst und vor jedem Zählen prüfst, ob Du diese noch zählen musst.

Beide Vorgehen sind gleichwertig. Ich will Dich da jetzt nicht überrennen mit Dingen die im Studium noch kommen werden, aber man kann Laufzeit und Speicherverbrauch betrachten ….
 
KonradN hat gesagt.:
Ja, das ist eine Lösung auf die wir hinaus wollten. Die Geldscheine sortiert man in der Regel (bildet Stapel gleicher Scheine) und zählt diese dann.
Zum Vergrößern anklicken....
Ich hab es schon geahnt, nachdem janeja mir den Hinweis gegeben hat. Schade nur, dass mein Prof mir nicht erzält, dass man arrays auch sortieren kann.

Die Vorlesungsfolie von letzter Woche hat 600 Seiten, aber die Infos die man zum lösen der Aufgaben braucht sind nicht drin.
Die 600 Seiten sind kein Witz
 
KonradN hat gesagt.:
Alternative könnte sein:
Ich gehe das erste Array Zahl für Zahl durch und zähle dann die Anzahl der Vorkommen.

Da zähle ich eine Zahl aber mehrfach - bei jedem Vorkommen.

Bei Deiner Beschreibung hattest Du etwas geschrieben, das ich so verstanden hatte, dass Du Ergebnisse aufschreibst. Das wäre dann also einfach, dass Du gezählte Zahlen merkst und vor jedem Zählen prüfst, ob Du diese noch zählen musst.

Beide Vorgehen sind gleichwertig. Ich will Dich da jetzt nicht überrennen mit Dingen die im Studium noch kommen werden, aber man kann Laufzeit und Speicherverbrauch betrachten ….
Zum Vergrößern anklicken....
Ja das mit dem Zählen der Anzahl jeden Scheins war anfangs meine Idee, dauert halt recht lange bei längeren Zahlen oder wie im Bsp. Scheinen.
Wenn man die Arrays erst sortiert dann kommt man logischerweise früher auf die Ungleichheit, wenn es denn eine gibt, oder verstehe ich das falsch?
 
Ach je … aber statt zu sortieren könntest du zur Not einfach jede Zahl zählen.

Also für jede Zahl aus Array1 ermittelst du die Anzahl in Array1 und Array2 und vergleichst diese.

Das ginge auch ohne jede weitere Verbesserung aber für jede Zahl gehst du alle Elemente beider Arrays durch. Also wenn die Arrays in Ihrer Länge sich verdoppeln, dann vervierfacht sich der Aufwand! Das ist also nicht so gut wenn man ggf mit großen Arrays umgehen muss.
 
überlebender hat gesagt.:
Ja das mit dem Zählen der Anzahl jeden Scheins war anfangs meine Idee, dauert halt recht lange bei längeren Zahlen oder wie im Bsp. Scheinen.
Wenn man die Arrays erst sortiert dann kommt man logischerweise früher auf die Ungleichheit, wenn es denn eine gibt, oder verstehe ich das falsch?
Zum Vergrößern anklicken....
Jetzt greife ich mal etwas vor. Bezüglich Laufzeit gibt es Laufzeitklassen. Da wird oft von der O Notation gesprochen (@mihe7 verbessere mich, falls ich Fachbegriffe falsch habe).

Die üblichen Sortieralgorithmen haben eine Laufzeit von O(n * log(n)) was besser ist als diese Quadratische Laufzeit der Vergleiche. Da bist du bei O(n*n) was schlechter ist.
Diese Sortierung musst du auf jeden Fall machen - damit hast du diesen Batzen immer. Der Check geht das Array einmal durch und hat daher O(n) und nur da kannst du früher abbrechen.

Das, was also die Hauptkosten verursacht, musst du voll durchziehen.
 
KonradN hat gesagt.:
Ach je … aber statt zu sortieren könntest du zur Not einfach jede Zahl zählen.

Also für jede Zahl aus Array1 ermittelst du die Anzahl in Array1 und Array2 und vergleichst diese.

Das ginge auch ohne jede weitere Verbesserung aber für jede Zahl gehst du alle Elemente beider Arrays durch. Also wenn die Arrays in Ihrer Länge sich verdoppeln, dann vervierfacht sich der Aufwand! Das ist also nicht so gut wenn man ggf mit großen Arrays umgehen muss.
Zum Vergrößern anklicken....
Ja das wird mir jetzt klar.

Also zuerst sortiere ich die Arrays.
Danach sage ich dem Compiler:
Wenn a[] != b[] -> false (grob)

Der Compiler geht jetzt auch jede Zahl durch, aber nur bis ein Unterschied auftaucht.

Also
11
1 2
---- Hier stoppt das Programm und Ausgabe -> false
11
12
11
12
21
22
21
22
2
 
Zuletzt bearbeitet:
KonradN hat gesagt.:
Jetzt greife ich mal etwas vor. Bezüglich Laufzeit gibt es Laufzeitklassen. Da wird oft von der O Notation gesprochen (@mihe7 verbessere mich, falls ich Fachbegriffe falsch habe).

Die üblichen Sortieralgorithmen haben eine Laufzeit von O(n * log(n)) was besser ist als diese Quadratische Laufzeit der Vergleiche. Da bist du bei O(n*n) was schlechter ist.
Diese Sortierung musst du auf jeden Fall machen - damit hast du diesen Batzen immer. Der Check geht das Array einmal durch und hat daher O(n) und nur da kannst du früher abbrechen.

Das, was also die Hauptkosten verursacht, musst du voll durchziehen.
Zum Vergrößern anklicken....
Ja gut ich versuche mir erstmal darüber Gedanken zu machen, wie ich das alles als Code schreibe.
Das Prinzip habe ich ja jetzt endlich verstanden. Danke allen für die Hilfe!
 
@überlebender bezüglich des CountingSort: das ist, was du bei den Geldscheinen schon hattest: du machst einfach n Stapel. Oder eine Strichliste. Bei Geldscheinen einfach - du hast nur sehr wenig. Da gehst du dann genau einmal die Scheine durch und gut ist es.

Aber wenn du 2 hoch 32 Möglichkeiten hast, dann wird die Strichliste sehr lang und das ist problematisch.

Wir brauchen nur das Zählen aber CountingSort würde dann am Ende nach dem Zählen die Strichliste durchgehen und die jeweilige Anzahl des Elements bereit stellen.

Das einfach, um diesen Begriff kurz zu erläutern.
 
KonradN hat gesagt.:
@überlebender bezüglich des CountingSort: das ist, was du bei den Geldscheinen schon hattest: du machst einfach n Stapel. Oder eine Strichliste. Bei Geldscheinen einfach - du hast nur sehr wenig. Da gehst du dann genau einmal die Scheine durch und gut ist es.

Aber wenn du 2 hoch 32 Möglichkeiten hast, dann wird die Strichliste sehr lang und das ist problematisch.

Wir brauchen nur das Zählen aber CountingSort würde dann am Ende nach dem Zählen die Strichliste durchgehen und die jeweilige Anzahl des Elements bereit stellen.

Das einfach, um diesen Begriff kurz zu erläutern.
Zum Vergrößern anklicken....
Danke für die Erklärung. 👍
 
KonradN hat gesagt.:
Wenn ich einen Stapel Geldscheine bekomme, dann zähle ich keine 5er, wenn es keine 5er gibt.
Zum Vergrößern anklicken....
Ja, allerdings war sein Ansatz genau das: 5er, 10er etc. zu zählen, auch wenn 0 als Ergebnis herauskommt (so hatte ich es zumindest verstanden). Das kann ich machen, wenn ich weiß, welche Werte es gibt (und die einigermaßen begrenzt sind), also z. B. mit echten Geld"werten": 500 €, 200 €, 100 €, 50 €, 20 €, 10 €, 5 €. Das sind 7 verschiedene Werte. Kenne ich die Werte im Vorfeld nicht, und will jeden Wert zählen, dann lande ich bei 4,2 Mrd. -> nicht sonderlich effizient 🙂
 
Man kann natürlich auch einfach streichen.

  1. Sind die Arrays A und B gleich lang? Falls nicht, gib false zurück.
  2. Für jedes Element aus A: suche ein Element mit dem gleichen Wert in B. Falls gefunden: streiche, das Element, ansonsten gib false zurück.
  3. Gib true zurück.
Beispiel:

A={1,2,3,4,5,1}, B={5,1,3,2,1,4}

Arrays sind gleich lang, also weiter.

1. Element aus A = 1 -> streiche das erste Vorkommen von 1 aus B -> B = {5,-,3,2,1,4}
2. Element aus A = 2 -> streiche das erste Vorkommen von 2 aus B -> B = {5,-,3,-,1,4}
3. Element aus A = 3 -> streiche das erste Vorkommen von 3 aus B -> B = {5,-,-,-,1,4}
4. Element aus A = 4 -> streiche das erste Vorkommen von 4 aus B -> B = {5,-,-,-,1,-}
5. Element aus A = 5 -> streiche das erste Vorkommen von 5 aus B -> B = {-,-,-,-,1,-}
6. Element aus A = 1 -> streiche das erste Vorkommen von 1 aus B -> B = {-,-,-,-,-,-}

Da jedes Element aus A in B gestrichen werden konnte -> true

Wäre z. B. B = {5,1,3,2,6,4} gewesen, dann hätte im 6. Schritt die zweite 1 aus A nicht in B gestrichen werden können -> false.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

ArrayList mit unbekannter Menge an Arrays die Arrays vergleichen
Antworten: 9
Arrays, Arrays, Arrays..
Antworten: 9
2 Arrays vergleichen u. das Array zurückgeben, welches kleinsten Wert beinhaltet.
Antworten: 3
Arrays vergleichen - Methode
Antworten: 1
Arrays in einer ArrayList miteinander vergleichen
Antworten: 12

Zurück
Oben