Such Algorithmus

[ome]

Hallo zusammen,

ich soll ein Algorithmus schreiben der folgendes erfüllt:

gegeben sind zwei Mengen, A der Länge n-1 und B der Länge n. Dabei soll ein fehlendes Element aus der Menge B gefunden werden. (A ist echte Teilmenge von .

Bsp.:

A={2,3,1}

B={4,1,3,2}

gesuchtes Element wäre hier eben die 4.

Meine Idee:

1. beide Arrays zusammen fügen.

2. paarweise gleiche Elemente löschen.

3. da unser zusammengefügter Menge immer eine ungerade Länge hat soll eben das übrig gebliebener Element ausgegeben werden.

Input: Array A, Array B, der Länge n;

-------C:= A+B;

-------for (int i=1; i<C.lenght; i++)

------------int k=0;

------------if (C[k] == C)

---------------delete (C[k], C);

------------endif;

-------endfor;

OUTPUT C;

ich habe hier nur das Problem, wenn mein gesuchtes Element schon das erste Element ist.

Ps: es soll eine Laufzeit von O(n) haben.

Schöne Grüße

Bearbeitet 28. April 2012 von ome

[flashpixx]

Benutze bitte die Code-Tags, um Quellcode zu posten!

Ps: es soll eine Laufzeit von O(n) haben.

Das kann man anhand Deines Quellcodes mit Hilfe der Vollständige Induktion beweisen.

Wie ist Deine Frage bezügl des Problems?

[ome]

mein Problem ist wann ich abbrechen kann. Weil mir ist aufgefallen das man die Länge von Arrays ja nicht ändern kann.

Ein weiteres Problem, ich setze erstes Element fest und dieses vergleiche ich und dabei werden Paare gelöscht. Aber ich komme in eine Endlosschleife, wenn das fehlende Element nicht in der Mitte des Arrays ist.

nja Wie löse ich das nun?

[Klotzkopp]

Welche Datenstruktur hast du denn nun genau? Erst schreibst du von Menge, jetzt von Array.

[ome]

nja die Aufgabe besagt das es 2 Mengen gibt. Aber im Code habe ich es als Array interpretiert.

[flashpixx]

Aber im Code habe ich es als Array interpretiert.

Das ist Definitionssache z.B. der Datentyp ArrayList (Java Platform SE 6) oder vector - C++ Reference sind dynamische Strukturen, dagegen ist ein array - C++ Reference eine statische Datenstruktur. Du verwenst Pseudocode und daher ist es Definitionssache, wie man eine Menge bzw. ein Array interpretiert. Rein von der mathematischen Definition (mathematische Menge) können Mengen auch unendlich sein. In der Informatik (informatische Menge) ist es immer endlich

[ome]

okay gut, dh. im Pseudocode kann ich Array lassen und wenn ich schreibe delete(bla blub) dann wird mein Array länge dementsprechend auch verkleinert?

[Gast runtimeterror]

Um die Differenz zweier allgemeiner unsortierter Mengen ohne Bitmap im Hintergrund zu finden ist mir kein Algorithmus bekannt, der eine Laufzeit von O(n) bietet.

Entweder müssen die Mengen sortiert sein

oder die Mengen müssen mit einer Art Bit-Array implementiert oder implementierbar sein.

In deinem Spezialfall gibt es aber eine einfache Lösung:

Alle Einträge der Menge der Menge B addieren und alle Einträge der Menge A subtrahieren. Das Ergebnis ist das überzählige Element. Die Position dieses Elements kann mit einer einfach O(n)-Suche gefunden werden.

In deinem Beispiel:

(4 + 1 + 3 + 2) - (2 +3 +1) = 4

[Gast runtimeterror]

Wenn ich mich nicht irre, dann dürfte dein Algorithmus gar nicht funktionieren. Um das von dir gewählte Beispiel zu verwenden:

C = A + B = [2, 3, 1] + [4, 1, 3, 2] = [2, 3, 1, 4, 1, 3, 2]

Deine Schleife würde das erste Element (C[0] = 2) mit allen anderen vergleichen und erst am Ende des Arrays einen Treffer landen und das Paar eliminieren. Anschließend wäre die Schleife beendet, ohne dass nach weiteren Paaren gesucht würde.

Die von dir angesprochene Endlosschleife kann bei deiner Zählschleife gar nicht auftreten: Der Zähler wird immer erhöht und das Limit wird verkleinert.

Die Variable k ist übrigens immer 0 und kann entfallen.

Ich hoffe, das hilft dir weiter.

Gruß,

runtimeterror

[ome]

klever habe mir zu schwer das ganze vorgestellt aber habe meine Variante in Java implementiert und es funktioniert auch in O(n).

werde es bei Bedarf posten.

Gruß

[Gast runtimeterror]

In Java würde ich das wie folgt implementieren:

O(n) Variante mit Bitmap (funkioniert nur für nichtnegative Werte mit nicht allzugroßem Wertebereich)

BitSet a = new BitSet();

// n * O(1) -> O(n)

a.set(2);

a.set(3);

a.set(1);


BitSet b = new BitSet();

// n * O(1) -> O(n)

b.set(4);

b.set(1);

b.set(3);

b.set(2);


// O(n)

b.andNot(a);


// O(n)

System.out.println(b.nextSetBit(0));

Allgemeinere Variante. Das Befüllen der Mengen ist durch die Sortierung etwas langsamer (O(n * log(n))), dafür kann die Differenzbildung in O(n) erfolgen - was Java evtl. aber nicht tut (dann müsste man das selbst implementieren).

// O(n * log(n))

SortedSet<Integer> a = new TreeSet<>(Arrays.asList(2, 3, 1));

// O(n * log(n))

SortedSet<Integer> b = new TreeSet<>(Arrays.asList(4, 1, 3, 2));

// O(n) oder O(n * log(n)) je nach Implementierung

b.removeAll(a);


// O(1) oder O(n) je nach Implementierung

System.out.println(b.iterator().next());

Alle anderen mir bekanten Verfahren arbeiten ähnlich oder haben eine Laufzeit von O(n²)

Ich bin auf deine Lösung gespannt

[ome]

Bitte schön

public class special {

	public static void main(String[] args) {

	int[] A = {4,3,5,1,10,9,8,7,2,6};         // Bsp.

	int B[] = {7,2,8,6,1,9,5,4,3};            // Bsp.

	int C[] = new int [A.length + B.length]; 


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

			C[i]=A[i];	  

		}

		for (int j=0, i=A.length; i < C.length; i++ ) { 

			C[i]=B[j];

			j++;	

		}

		for (int i=C.length/2+1 ,k=0; i<C.length;i++) {

			if(C[k]==C[i]){

				C[k]=0;

				C[i]=0;

				k++;

				i = C.length/2+1;

			}

			if(C[k]!=C[i]&& i==C.length-1) {

				System.out.print(C[k]);

			}

		}

	}

}

O(n)+O(n)+O(n) Є O(n)

[Gast runtimeterror]

Dein Algorithmus hat eine Laufzeit von O(n²), da du den Schleifenzähler zurücksetzt - das hat denselben Effekt, wie zwei ineinander verschachtelte Schleifen. Ein kurzer Test zeigt:

1 bzw. 2 Einträge -> 1 Schleifendurchlauf

4 bzw. 5 Einträge -> 10 Schleifendurchlauf

9 bzw. 10 Einträge -> 45 Schleifendurchlauf

Zudem gibt's noch ein paar Fehlerchen:

Folgende Befüllung findet die falsche Lösung "7" statt "10"

int[] A = { 4, 3, 5, 1, 9, 8, 7, 2, 6, 10 }; // Bsp.

int[] B = { 7, 2, 8, 6, 1, 9, 5, 4, 3 }; // Bsp.

Folgende Befüllung findet keine Lösung:

int[] A = { 1 }; // Bsp.

int[] B = { }; // Bsp.

Das Zusammenführen der beiden Arrays erscheint mir nicht als sinnvoll:

k durchäuft nur die Indizes von A

i durchläuft nur die Indizes von B

Wenn man die Arrays getrennt lässt und ein wenig optimiert, wird man sehen, dass der Algorithmus mit einer Zwei-Schleifen-Lösung identisch ist.

Schöne Grüße,

runtimeterror

[ome]

mist, hätte ich vorher wohl besser gepostet

najut damit das wenigstens das richtige Ergebnis immer ausgibt muss man statt

i = C.length/2+1;

folgendes sein:

i = k+1;

ich sollte vllt noch erwähnen das die Arrays nicht leer sein dürfen. Aber ich habe mich um Spezialfälle nicht mehr gekümmert da ich es ja nur als Pseudocode angeben sollte. Hast aber recht.

[Gast runtimeterror]

Das hier wäre dein Algorithmus mit den oben angesprochenen Umformungen und der Fehlerbehebung:

next: for (int k = 0; k < A.length; k++) {

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

		if (A[k] == B[i]) continue next;

	}

	System.out.println("Lösung: " + A[k]);

}