Rückkehr position der Wert in einem 2D-array, Java
Ich bin müde. Das muss einfach sein. Holz... für.... Bäume....
Ich versuche, die Rückkehr der position von einem bestimmten Wert in einem 2D-array.
Habe ich ein double array [300][300].
Alle Werte, die in ihm enthalten sind 0 mit Ausnahme von einem, ist 255.
Wie Schreibe ich eine Methode zurückzukehren, die [ich][j]. Position von 255?
Vielen Dank im Voraus.
- Sind diese Werte sortiert? Wenn dem so ist, gibt es
O(log n)
(komplett sortiert) oderO(n log n)
(nur Zeilen oder Spalten sortiert) Versionen. Ansonsten sind Sie stecken mitO(n^2)
, als zur Verfügung gestellt wurde. - Nein, nicht sortiert.
- was haben diese O Dinge bedeuten. Sie machen für mich keinen Sinn und deshalb kann ich es nicht verstehen, Ihren Wert
- es nennt sich Big O-notation. Es ist ein einfaches Maß für die erwartete Anzahl der Schritte, die erforderlich sind, um etwas zu tun.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Einfach iterieren über alle Elemente, bis Sie finden, das ist
255
:Dies funktioniert:
Dies ist möglicherweise der Schnellste, aber. Es prüft ab, in jeder Ecke, progressiv arbeiten nach innen zum Zentrum, zuerst horizontal, dann vertikal:
i=0..length/2
undj=0..length/2
statt zu verhindern, double-checking. (Vielleicht off-by-one).length/2+1
.i
über die gesamte Länge, obwohl.n^2
ist worst-case. Der Durchschnittliche Fall ist noch schneller, da es überprüft, beide Seiten vor der re-Iteration. Am effizientesten können zwei weitere Prüfungen (hinzufügen als zweite code-Beispiel).Können Sie binäre Suche für jede Spalte.
Verwenden für - Schleife für die Iteration über jede Spalte, wie es ist ein 2d-array.
Sobald Sie alle Zeilen aus der bestimmten Spalte, die Sie Durchlaufen haben ( das wäre ein anderes array), eine binäre Suche auf Sie.
Bedingungen Gelten:
1. Wenn das array sortiert ist .
2. Wenn Sie sicher sind, dass nur ein element gibt es in jeder Spalte. ( Keine Duplikate).
3. Wenn es Duplikate in den Zeilen( lineare Suche) .
Ich hoffe, es hilft. Fühlen Sie sich bitte frei zu Fragen, wenn Sie noch im Zweifel sind 🙂