Ich habe ein sequenzielles ungeradzahliges Array beginnend bei 3. So x = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 ...}. Ich frage mich, ob es einen schnellen Weg gibt zu finden, bei welchem Index das Quadrat einer Zahl n ist. Also, wenn n 5 ist, suche ich, wo 25 im Array ist. Gerade jetzt habe ich ((n) * (n - 1)) was ich dem aktuellen i Index hinzufüge. Gibt es etwas schneller?Das Quadrat einer Zahl in einem sequentiellen Array von Wahrscheinlichkeiten finden
Ihr Array besteht aus aufeinander folgenden Zahlen gemacht und es sortiert ist, weil es dafür bildet eine mathematische arithmetische Progression mit Differenz 1 und die ersten Elemente als 3, so bei Index i wir a[i]=i+3 und so i=a[i]-3 haben.
So den Index des Platzes von n zu finden nsqrn*n sein lassen, nsqr Index ist einfach nsqr-3, das ist ein O(1) Algorithmus.
Um es allgemein zu machen, wenn wir aufeinander folgenden sortierten Zahlen haben, die mit a0 und unterscheiden sich von d beginnen, um herauszufinden, wo der Platz von n ist wir (nsqr-a0)/d tun.
Verwenden Sie binäre Suchalgorithmus, O (log n) Komplexität – bigbounty
dieses Array ist kein Array von Chancen, es beginnt nur mit einer ungeraden Zahl, trotzdem ist das Array immer aus aufeinanderfolgenden Nummern gebaut? wenn nicht, wird es immer sortiert? – niceman
@niceman es wird immer aus fortlaufenden Nummern gebaut und immer in aufsteigender Reihenfolge sortiert – user7252850