1
Wir erhalten eine quadratische Matrix, die mit Zahlen aus [1, n * n] in einer Reihe Hauptform gefüllt ist. Wir müssen das k-te Element finden, wenn wir es in einer spiralförmigen Reihenfolge durchlaufen. Die einzige Lösung, die ich mir vorstellen konnte, war, eine spiralförmige Traversierung durchzuführen und einen Zähler für die Anzahl der durchlaufenen Elemente aufrechtzuerhalten. Wenn Zählerwert k wird, drucken wir die Nummer in dieser Instanz.K-tes Element in einer spiralförmigen Traversierung einer speziellen Matrix
Kann dies in weniger als O (n * n) gelöst werden? Wenn ja, dann wie das gleiche Problem lösen, wenn Matrixelemente mit zufälligen Elementen?
Die Anzahl der Elemente in jedem Ring von dem vorherigen unterscheidet Ring um 8. – user3386109
Sie können grob in O dieses Problem lösen (1); Sie müssen die ganzzahlige Quadratwurzel von 'n * n-k' finden. Mit der babylonischen Methode zum Beispiel können Sie das in 'log log n * n'-Iterationen lösen (was' O (log log n) 'ist) – rici