Mit Bezug auf die question, habe ich die akzeptierte Antwort Java Collections API verwendet, um den Index zu erhalten. Meine Frage ist, gibt es so viele andere Methoden, um das gegebene Problem zu lösen, welches die optimale Lösung wäre?Algorithmuskomplexität: Finden des Startindex eines Sub-Array in einem größeren Array
O(n^2) Zeit dauern wird,O(nlog n) ZeitO(nlog n) ZeitO(k * n) Zeit mit einem anderen Overhead und zusätzlichem Platz nehmen.O(n^2) Zeit als seine Verwendung nativer Algorithmus unter der HaubeSie es zusammen mit der Art und Weise optimal tun können mit Knuth–Morris–Pratt algorithm in linearer O(n + m) Zeitkomplexität oben erwähnt, wo n und m sind die Längen der beiden Arrays.
KMP-Algorithmus ist im Grunde ein Muster-Matching-Algorithmus (die Startposition einer Nadel im Heuhaufen zu finden), der auf Zeichenkette funktioniert. Aber Sie können es einfach für Integer-Array verwenden.
Sie können einige Benchmark-Tests für alle diese Implementierungen durchführen und wählen, welche für Ihre Anforderungen effizient genug ist.
Danke. Aber es scheint, dass der gegebene Algorithmus für Strings ist. Ist es gut für Integer-Arrays? – deadbug
Ja, anstatt Zeichenarray (string) zu vergleichen 'str1 [i] == str2 [j]' wird das Ganzzahlarray 'arr1 [i] == arr2 [j] 'verglichen. Ein Vergleich des Zeichens von Zeichenkette vergleicht ein Byte und für Ganzzahl seine vier Bytes. Nichts anderes als das. –
Probieren Sie es aus und Benchmark sie? Obwohl ich sagen würde, dass derjenige, der den geringsten Code erfordert, oft der beste ist. – UnholySheep