Dies ist eine Interviewfrage. Bei einem Array von ganzen Zahlen schreiben Sie eine Methode, um die Indizes m und n zu finden. Wenn Sie die Elemente m bis n sortieren, wird das gesamte Array sortiert. Minimiere n-m. d. h. kleinste Sequenz finden.
Die ganzen Zahlen vor m sollten aufsteigend und kleiner als ganze Zahlen (oder gleich) sein.
Beginnen Sie beim ersten Element und stoppen Sie beim ersten Abnehmen. (Unterfeld SA)
Finde Minimum nach. (MIN)
Der Startpunkt liegt unmittelbar hinter der maximalen Ganzzahl in SA, die kleiner als (oder gleich) MIN ist. (m ist gefunden)
O (N)
Machen Sie Ähnliches für n.
Sie müssen vier Dinge im Auge behalten:
Beginnen Sie damit, einen vorläufigen Wert für 1 und 2 herauszufinden, indem Sie das Array vom Anfang bis zum Ende absuchen, bis Sie einen falsch platzierten Wert gefunden haben.
Dann scannen Sie alles nach Ihrer vorläufigen 1, um die Mindestanzahl zu finden. Dies ist Ihre 3. Finden Sie 4 auf die gleiche Weise.
Sie gehen nun zurück durch den Startbereich des Arrays, bis Sie den Ort gefunden haben, an dem der Mindestwert liegen sollte. Dies ist die genaue Antwort auf 1 und auch Ihre m .
Finden Sie n auf die gleiche Weise, indem Sie durch die Endregion zurückverfolgen, um herauszufinden, wo die maximale Anzahl sein sollte.
Tags und Links algorithm