zwei Arrays nach gemeinsamme Elemente suchen?

[gustav-mega]

Hallo,

ich bin neu hier, und hoffe dass ich auch hier richtig bin ) . Mein Problem ist folgendes:

Ich habe zwei Arrays mit Zahlen, und möchte alle gemeinsamme Zahlen von den zwei Arrays in einem anderen Array speichern, kann jemand mir vielleicht sagen, wie ich das machen könnte?

Gruß,
G.M.

 

[DesertFox]

meinst du sowas in die richtung?

int k = 0;
for (int i=0; i<array1.length; i++){

for (int j = 0; j<array2.length; j++){

if (array1[i] == array[2]){

array3[k] = array1[i];
k++;

}
}

 

[gustav-mega]

erstmal Vielen Dank für die Antwort , ja so etwas suche ich und Du meinst wahrscheinlich in Deinem Code in der Zeile 6 statt "array[2]" doch "array2[j]", oder? aber ich suche nach einer anderen Algorithmus, in der so wenige Elemente wie möglich vergelichen werden, da Deine Algorithmus doch eine "Brute Force Algorithmus" ist.

Gruß,
G.M.[/code]

 

[Roar]

aber ich suche nach einer anderen Algorithmus, in der so wenige Elemente wie möglich angeschaut werden,

wie soll das denn anders gehe nals jedes element des einen arrays mit jedem des anderen zu vergleichen??

 

[DesertFox]

ähh ja sich mein ich doch, habs halt nur geschwind runtergetippt.
Aber wie soll des mit weniger prüfungen gehen? In meinem Fall werden jede Zahl im ersten Array mit jeder Zahl im zweiten array verglichen, und keine mehr, aber wenn man weniger prüft, kommen doch falsche ergebnisse raus!

 

[gustav-mega]

Das ist auch genau mein Problem, da es von uns das verlangt worden ist .

Gruß,
G.M.

 

[DesertFox]

OMG, liefer ihm die lösung von mir, es gibt keine andere!!! Man was sind des für Aufgaben, oder für Leute, die die machen? Wie will man da Java lernen, wenn man unlösbare aufgaben bekommt??

 

[Beni]

Zuerst mal die Arrays sortieren... und dann muss man nicht mehr jedes Element mit jedem vergleichen.

Ein Sortieralgorithmus benötigt nur O( n log n ) Zeit, im Gegensatz zum Vergleichen (was O( n^2 ) benötigt), ist also schlussendlich schneller.

 

[DesertFox]

ähhhm ok, dann zieh ich meine aussagen über den Aufgabensteller zurück, SRY . Aber darauf wär ich net gekommen.

 

[gustav-mega]

Vielleicht eine dumme Frage , aber wenn ich auch zwei sortierte Arrays habe, muss ich doch trotzdem die Elemente einzeln vergleichen, oder?

Gruß,
G.M.

 

[Beni]

Du kannst sowas zusammenschreiben (ich habs nicht getestet).

int[] a = ...
int[] b = ...

// a und b sind die beiden sortieren Arrays
// Dann kannst du sowas schreiben:

int indexA = 0;
int indexB = 0;

int stopA = a.length;
int stopB = b.length;

while( indexA < stopA && indexB < stopB ){
  if( a[indexA] < b[indexB] )
    indexA++;
  else if( a[indexA] > b[indexB] )
    indexB++;
  else{
    // a[indexA] und b[indexB] sind jetzt gleich, also speichern.
    indexA++;
    indexB++;
  }
}

[Edit: Sortieren kann man mit java.util.Arrays#sort]

 

[gustav-mega]

OK, dann werde ich es einfach probieren. Aber trotzdem VIELEN DANK .

Gruß,
G.M.

 

[bygones]

wenn du zufaellig das eine als Set und nicht als Array hast geht auch: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Set.html#retainAll(java.util.Collection)

 

[gustav-mega]

Hallo,

die Algorithmus von Beni funktioniert wunderbar, aber dass ich auch richtig verstehe, der Vorschlag von DesertFox hat eine Laufzeit von O(n^2) und der von Beni O(2*n)=O(n), oder?

Gruß,
G.M.

 

[Beni]

Nein, O( n log n ), weil man bei mir zuerst noch sortieren muss!

 

[gustav-mega]

aber wenn die Liste sortiert wäre, hätte man dann eine Laufzeit von O(n) gehabt und log n ist doch die Laufzeit für Sortieren, oder?

Gruß,
G.M.

 

[Beni]

O(n log n) ist die Laufzeit fürs Sortieren, O(n) für das Vergleichen, ja

 

[gustav-mega]

muss es aber nicht heissenO (n*(n log n)) aber warum ist dann Gesamtlaufzeit O( n log n )?

Gruß,
G.M.

 

[Beni]

Zuerst sortiert man, dann wird verglichen. Das ergibt O( n log n + n )
Aber das ist = O( n log n ), weil n viel kleiner als n log n ist.

 

[gustav-mega]

DANKE .

Gruß,
G.M.