arrays

julia123

Erfahrenes Mitglied
hi leute,

hab hier ein kleines Problem. Ich möchte mein array auf dublikate prüfen.

Code:
public static void main(String[] args) {
		int[] field = { 2, 17,2,3,5,6 };
		//System.out.println(field.length);
		//System.out.println(field[0]);
		System.out.println(duplikatFeld(field));

	}

	static boolean duplikatFeld(int[] x) {
		if (x.length == 1) {
			return true;
		} else {
			for (int i = 0; x.length >= i; i++) {
				// untere schleife prüft auf dublikate
				for (int i2 = 0; x.length >= i2; i2++) {
					if (x[i] == x[i2]) {
						return false;
					} else {
						break;
					}
				}
			}
		}

Ich bekomme eine warnung dass, i2++ nich ausgeführt wird ich vermute das liegt am return.
 

Der Wolf

Erfahrenes Mitglied
Hallo,

die untere Schleife wird auf jedenfall sofort unterbrochen, denn entweder sind beide Felder gleich, dann wird aus der kompletten Schleife heraus gesprungen und "false" zurück gegeben, oder aber, die beiden Felder sind nicht gleich und die Schleife wird durch das "break" beendet. Eine dritte Möglichkeit gibt es da ja nicht.

Wenn du auf Duplikate testen willst könnte folgendes Beispiel (Achtung, nicht getestet, rein aus dem Kopf) vielleicht helfen.

Java:
static boolean duplikatFeld(int[] x) {
    boolean result = false;
    for (int i = 0; x.length > i; i++) {
        for (int j = 0; x.length > j; j++) {
             if (x[i] == x[j]) {
                    result = true;
                    break;
             }
        }
    }
    return result;
}


Gruß,
Wolf
 

julia123

Erfahrenes Mitglied
das läuft auch nicht. das leigt glaube ich daran das wir immer die selbe stelle prüfen also x[0]==x[0].
ich glaub das ist das problem.
 

Der Wolf

Erfahrenes Mitglied
das läuft auch nicht.

ist eine etwas magere Aussage.

Aber das eigentliche Problem ist mir gerade aufgefallen. Der zweite Laufindex, j, darf natürlich nicht bei 0 starten, sondern muss bei 1 anfangen. Also

Java:
for (int j = 1; x.length > j; j++) {

denn
Code:
x[i] == x[j]
für i = j = 0, da hast du natürlich recht.

Gruß,
Wolf
 

julia123

Erfahrenes Mitglied
ja, aber aber wenn es bei 1 anfängt wird es wieder nicht funktionieren...
weill wenn die Schleife dann bei Zeile3(siehe oben) auf 1 springt wird wieder x[1]==x[1] verglichen.
Und wenn man angenommen x[i+1] implementien würde käm der Fehler outofbounds also zu großes array. Ich hofe ich hab das korrekt erklärt.
 

sheel

I love Asm
Da hast du Recht, deshalb eine korrigierte Version hier:
Java:
static boolean duplikatFeld(int[] x) {
    boolean result = false;
    for (int i = 0; x.length > i; i++) {
        for (int j = i + 1; x.length > j; j++) {
             if (x[i] == x[j]) {
                    result = true;
                    break;
             }
        }
    }
    return result;
}
j beginnt immer bei i+1
Damit wird für [0] alles außer [0] auf Gleichheit geprüft,
für [1] alles außer [0] und [1], also ab [2] usw...

Man muss die Elemente vor dem aktuellen i nicht mehr überprüfen,
weil wenn ein Element davor den selben Wert hätte wäre das schon erkannt worden,
als dieses Element das aktuelle i war.
 

HonniCilest

Erfahrenes Mitglied
Beispiel du vergleichst
0 1 2 3 3 4

Du hast 2 Möglichkeiten:
a) - empfohlen wegen Laufzeit - Die erste Schleife läuft von index 0 bis index 4 (also eins vor Ende) und die zweite schleife startet bei i+1.
Du würdest also in dem Beispiel so vergleichen: 0-1 0-2 0-3 0-3 0-4 1-2 1-3 1-3 1-4 2-3 2-3 2-4 3-3 --> FALSE
b) Du fügst eine weitere Bedingung hinzu, die besagt i1!=i2
Du würdest so vergleichen: 0-0 (enfällt wegen zweiter Bedingung) 0-1 0-2 0-3 0-3 0-4 1-0 ... Und hier hast du eine überflüssige Operation, denn der Vergleich 0-1 und 1-0 ist der gleiche, deswegen startet die innere Schleife eigentlich bei i+1.
 

julia123

Erfahrenes Mitglied
ich hätte da noch eine anschliessende Frage. Angenommen ich will das jetzt rekrusiv lösen.
wie kann man das realisieren.
Ich wäre echt dankbar für eine Musterlösung( auch wenn dies nicht erlaubt ist).
Reksion heißt ja durch sich selbst aufrufen usw. Hier sind es jedoch 2 Schleifen.
Naja vielleicht kann mir ja jemand weiter helfen.
ansosnten vielen dank. Dass oben hab ich verstanden!
 

HonniCilest

Erfahrenes Mitglied
Wenn du weiterhin mit Arrays arbeitest würde ich dir bei diesem Beispiel keine Rekursion empfehlen. Du müsstest entweder einen Zeiger auf die aktuelle Position mitgeben, oder dir ein um 1 kleineres Array zusammenbasteln. Letzteres hat natürlich verstärkt Auswirkung auf die Laufzeit.

Wenn du stattdessen aber mit einer Liste arbeitest könntest du hier einfach das letzte oder erste Element der Liste entfernen.
 
Zuletzt bearbeitet:

sheel

I love Asm
Oder anders: Ist es erlaubt, weitere Parameter dazu zu erfinden?
Oder darf nur dieser eine, wie oben im Code, verwendet werden?

Andere Frage, nur um sicher zu gehen:
In der Angabe ist nicht zufällig von sortierten Arrays die Rede?
Falls doch, bitte sagen.
Die Lösung oben ist dadurch zwar nicht falsch,
aber es würde etwas einfacher (und schneller) auch gehen.
Und das wird der Lehrer dann auch sehen wollen,
falls extra von sortierten Arrays geschrieben wird.