Ich wurde diese Frage heute in einem Interview gestellt. Ich habe eine Lösung ausprobiert, würde aber gerne wissen, ob es eine bessere Lösung gibt:
Frage : Ich habe eine ArrayListe von 500.000 Elementen, so dass der Wert jedes Elements der Arraylist gleich dem Index ist. Für ex: list.get (0) = 0; list.get (1) = 1 ... usw. Aber nur ein Element ist nicht synchron mit dieser Reihenfolge [d.h. list.get (i)! = I]. Wie finden Sie das Element?
Meine Antwort : Iterieren Sie die Liste mit mehreren Threads, wobei jeder Thread einen bestimmten Splice der Arraylist behandelt, wenn Sie list.get (i) mit i vergleichen. Wenn das Element gefunden wurde, setze eine boolesche Variable, um anderen Threads anzuzeigen, dass das Element gefunden wurde.
Gibt es eine Möglichkeit, dieses Problem zu lösen, ohne die Liste zu überarbeiten? Oder ein besserer Weg?
Im schlimmsten Fall müssen Sie jedes Element untersuchen, damit Sie die Komplexität der O(n) -Zeit nicht verbessern können.
In diesem Sinne ist der beste Algorithmus, die Array-Liste von Anfang bis Ende zu scannen. Auf diese Weise nutzen Sie die verfügbare Speicherbandbreite optimal.
Es ist mir nicht ganz klar, wie oder warum Threading ins Bild gekommen ist. Es scheint fehl am Platz zu sein. War das ein Teil der Frage?
Sie können nicht besser als O(n) .
Und zweitens denke ich, dass es eine schlechte Idee ist, über Threads und Multithreading bei diesen Problemen zu sprechen. Sie sind überhaupt nicht von Interesse. Am Ende hast du eine Laufzeit von O (was auch immer) wo deine Konstante sowieso entfernt wird.
Vielleicht meinte der Interviewer ein sortiertes Array mit Elementen von 0 bis n-1 mit Index 0 bis n-1. Und dann verschiebe ein Element an eine andere Position. Das bedeutet aber, dass alle übrigen Elemente unterschiedliche Indizes haben! In diesem Szenario können Sie Ihre Suche mit der binären Suche verbessern:
Dann können Sie das Element in O(log n) erhalten. Beginnen Sie in der Mitte und prüfen Sie, ob der Index dem Element entspricht. Wenn es gleich ist, mache dasselbe mit dem oberen Teil der Hälfte, wenn nicht, benutze den anderen Teil.
Die Antwort ist: eine Iteration. Ihre Erwähnung der Nebenläufigkeit der Ursache ist etwas, nach dem sie fischen.
Tatsächlich ist seit java 8 die Lösung, ob parallel oder nicht, einfach. Ich denke die meisten hätten gebracht:
%Vor%Tags und Links algorithm java collections