Array auf Subarray überprüfen

[Kuru]

Hallo, zurzeit bereite ich mich auf eine Klausur über Java vor.
Nun wurde mir zur Übung eine Aufgabe gestellt in welcher ich zwei Arrays vergleichen soll.

Die Aufgabenstellung lautet:
"Implementieren Sie eine statische Methode findeSubarray (int [] werte, int [] subarray) in Java, die zwei Integer-Arrays werte und subarray als Argument erhält. Die Funktion soll testen, ob das Array subarray im Array werte zusammenhängend vorkommt. Die Methode soll true zurückgeben, falls das Teilarray gefunden wurde, ansonsten false. Sie können davon ausgehen, dass beide Arrays eine Länge von mindestens 1 haben."

Ich habe bereits eine Klasse für diese Aufgabe erstellt, welche allerdings unnötig kompliziert erscheint und zudem nicht fehlerfrei ist ^^.

public class arraytest {

	
	public static void main(String[] args) {
	
		int[] Array1={2,3,4,5,6};
		int[] Array2={3,4,5};
		
	findearray (Array1,Array2);	

	}

	public static boolean findearray (int [] werte, int [] subarray){
		int i = 0;
		int t = 0;
		boolean b = false;


		while (werte[i]<=werte.length){
			i++;
			if (werte [i] == subarray[i]){
				t++;
				if (t == subarray.length){
					
					b = true;
				}
			
				}
			else {
				
				b = false;
			}
			if (b= true){
				System.out.println("true");
			}
			else {
				System.out.println("false");				
			}
			
			}
		return b;		
			}	
}

Deswegen hätte ich die Frage ob sich diese Fragestellung auch simpler umsetzen lässt.
Vielen Dank, mfg Kuru

 

[Marco13]

for-Schleifen wurden noch nicht durchgenommen?

Abgesehen davon, und davon, dass man gleich 'return true' schreiben könnte, statt es in 'b' zu speichern kann man da nicht sooo viel einfacher machen (ich würde es eher mit zwei Schleifen schreiben, aber es könnte auch mit einer gehen..)

 

[anti-held]

eine Lösung könnte sein:

	public static boolean findearray(int[] werte, int[] subarray) {
		for (int i = 0; i < werte.length - subarray.length; i++) {
			for (int current = 0; current < subarray.length; current++) {
				if (werte[i + current] == subarray[current]) {
					if (current == subarray.length-1) {
						return true;
					}
				} else {
					continue;
				}
			}
		}
		return false;
	}

 

[Kuru]

Danke für die Antworten

@Marco13
Ehrlich gesagt wurden for Schleifen schon durchgenommen. Der Stoff der Klausur ist mir derzeit noch etwas unübersichtlich, da ich ca. 90% des Semesters nicht sehr aktiv am Lernen war. Die-for Schleife ist mir noch nicht so geläufig ^^. Den Boolean b sollte ich wohl löschen...

@anti-held
Danke für die Lösung, der perfekte Denkanstoß für mich, da ich gerade noch am Überlegen bin wie diese Methode funktioniert. Die zwei for-Schleifen sind mir nicht ganz ersichtlich.

 

[anti-held]

In der ersten Schleife wird vom ersten Wert im werte Array soweit gegangen, bis nur noch die Länge des Subarrays in die übriggebliebene Länge des Arrays passt.
In der 2. schleife wird über das komplette Subarray iteriert, und immer geschaut, ob die einzelnen Werte übereinstimmen.
Falls das einmal nicht der Fall ist, wird abgebrochen.
Falls dann das letzte Element des Subarrays erreicht ist, und immer noch die Werte übereinstimmen, wird true zurückgegeben.
Wenn alles beendet ist, und nicht eine Übereinstimmung gefunden wurde, dann wird false zurückgegeben.
Hoffe man kann das verstehen xD

 

[Kuru]

Vielen Dank für deine Erklärung, leider bin ich trotz intensivem Überlegem dem Lösen des Rätsels nicht näher gekommen ;D
Es liegt weniger an deiner Erklärung sondern mehr an meinem fehlenden Verständnis von Java ^^

Nehmen wir an ich hätte ein Array {3,7,1,5,2,8} und ein Subarray {7,1,5,2}.

So geht die erste for-Schleife durch {3,7,1}?

Nun wird das Subarray komplett durchlaufen... wobei zunächst Stelle 2 von Array mit Stelle 1 von Subarray verglichen wird? Also 1 mit 1 = true.

Dann folgt Stelle 4 von Array mit Stelle 2 von Subarray, also 2 mit 5 = false? xD

Habe ich einen gravierenden Denkfehler in der Ausführung von Schleifen und Arrays ? Sitze seit einer halben Stunde mit einem Blatt Papier vor dem Code und durchlaufe Arrays im Kopf ^^.
Langsam fühle ich mich etwas verwirrt. ???:L

 

[anti-held]

es wird nicht nacheinander gemacht, sondern geschachtelt!
Das heißt, erst wird 3 mit 7 verglichen...stimmt nicht...
also wird 7 mit 7 verglichen...dann 1 mit 1...dann 5 mit 5 und zu guter letzt 2 mit 2!
Da das die letzte stelle vom subarray war und auch stimmt, wird true zurückgegeben.

 

[MujoA]

Hallo,

ich arbeite gerade an der selben Aufgabe. Soweit ich das bei der Lösung hier erkennen kann,
überprüft die nur, ob alle Werte des Subarrays im anderen Array vorkommen.
Es wird aber nicht die Reihenfolge berücksichtigt. In der Angabe steht ja, dass die Werte
zusammenhängend vorkommen sollen.

Also ist z.B. a = {2,5,7} kein Subarray von b = {1,2,3,4,5,6,7,8,9}.

Die Lösung dafür habe ich nicht, wollte es aber nur anmerken

Ich denke, man muss prüfen, ob a[0] == b[0]. Wenn das so ist, dann prüfen ob a[1] == b[1],
a[2] == b[2] usw. bis das Ende vom Subarray erreicht ist.
Falls die Gleichheit aber irgendwo nicht stimmt, dann bei b[1] anfangen und wieder prüfen ob
a[0] == b[1], a[1] == b[2] usw. und wenn das irgendwo nicht mehr stimmt, dann prüfen ob
a[0] == b[2], a[1] == b[3]...sozusagen den Anfang immer um 1 verschieben bis man ein solches
Subarray findet oder das zu testende Subarray ab irgendeinem b nicht mehr in b reinpassen würde.

Wie man das jetzt noch schön implementiert, versuche ich gerade herauszufinden. Mit Java kenne
ich mich noch nicht so sehr aus...

...ob es in der Klausur was bringt, einen Algorithmus in Worten hinzuschreiben? hahah

 

[anti-held]

nene...meine Lösung gibt schon nur bei ein zusammenhängenden Subarray true zurück.

 

[MujoA]

Also ich habe es bei mir getestet und bei {1,2,3,4,5,6,7,8,9} und {2,5,7} wird true ausgegeben.
Könnte auch was falsch gemacht haben..wobei ich es direkt von hier kopiert habe.

 

[anti-held]

ok...du hast recht!
habs leider nicht getestet gehabt!
Der Fehler ist, dass ich continue statt break geschrieben habe.
Danach funktioniert es einwandfrei!
Das break ist das abbruchkriterium für die innere schleife.
Beim continue bricht er die schleife nicht ab und kann so auch true zurückliefern.
sry!

 

[anti-held]

Fehlerfreier Code:

Spoiler: Code

    public static boolean findearray(int[] werte, int[] subarray) {
        for (int i = 0; i < werte.length - subarray.length; i++) {
            for (int current = 0; current < subarray.length; current++) {
                if (werte[i + current] == subarray[current]) {
                    if (current == subarray.length-1) {
                        return true;
                    }
                } else {
                    break;
                }
            }
        }
        return false;
    }

 

[MujoA]

Nicht ganz

Bei {1,2,3,4,5,6,7,8,9} und {7,8,9} wird false ausgegeben, obwohl {7,8,9} ein Subarray ist.
Da wird wohl das letzte Element nicht mit einbezogen ({6,7,8} liefert noch true).

Habe mal oben bei der Bedingung einfach "+1" eingefügt und dann schien es zu funktionieren. Also

i < werte.length - subarray.length + 1

Ich wünschte ich wäre im Programmieren so gut wie im Fehler finden

 

[anti-held]

hm...xD
vill sollte ich mir vor den Posts mehr Zeit nehmen um den Code zu testen!