Guten morgen, ich beschäftige im Moment zum ersten mal mit einer Programmiersprache und habe ein Problem, was ich zwar lösen kann, aber mit einer miserablen Laufzeit. Problem: Es ist gegeben ein Array array ={1,2,3} und eine LinkedList<int[]> die wie folgt ausschaut linkedList={{1,2,2},{1,3,2},{3,2,1}}. Geprüft werden soll, dass jede Untermenge in linkedList (nennt man dies Untermenge?) ein oder mehrere, aber nur Elemente aus dem Array hat. Wenn in einen der Untermengen eine 7 vorkommt und diese ist nicht im array={1,2,3}, sollte es erkannt werden. Meine brute force Lösung waren 3 Forscheleifen, wobei ich jede Untermenge in der ersten in einen Array packe und in den nächsten zwei Forschleifen die einzelnen Elemente der arrays vergleiche => Laufzeit O(n^3), also unschöne Nummer. Leider fehlt mir etwas der Rüststoff, wie ich dieses Problem ganz einfach löse und es wäre nett, wenn mir hier Jemand helfen könnte.
Eine Methode wäre statt dem Array ein Hash map zu programmieren. Du hast dort quasi ein Array von Arrays. Fürs erste Array nutzt du den gesuchten Wert (oder den Hashwert eines Objekts), bzw. einen Teil davon, als Index. Im ausgewählten Array suchst du dann normal danach. Im Idealfall gibt es nur 1-2 Einträge pro Array, womit dass dann sehr schnell geht. Jenachdem bekommt man dann praktisch O(1). Oder kannst du die Elemente der Listen und Arrays sortiert halten? Dann könntest du eine Schleife mit 2 Laufwariablen machen. Wenn a<b, nächstes a. Wenn b<a, nicht gefunden. Wenn a==b, nächstes b. Natürlich gibt es noch viele andere Strukturen und Algorithmen, die man nehmen könnte. Die sind mir halt spontan so eingefallen.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.