Car Fleet

Q: Wie hoch ist die Zeitkomplexität von Car Fleet?

Das Sortieren nach Position benötigt O(n log n) und der Durchlauf mit einem Stack benötigt O(n) , daher beträgt der Gesamtaufwand O(n log n) Zeit und O(n) Speicher. Jedes Auto mit jedem vorausfahrenden Auto zu vergleichen, benötigt O(n²) .

Q: Wie vergleichst du Ankunftszeiten ohne Gleitkommazahlen?

Die Ankunftszeit beträgt dist / speed . Da die Geschwindigkeiten positiv sind, gilt d1 / s1 > d2 / s2 genau dann, wenn d1 × s2 > d2 × s1 . Beide Seiten sind ganze Zahlen bis zu 10^12 , daher berechne sie mit einem 64-Bit-Typ und der Vergleich ist exakt, sodass keine Rundung berücksichtigt werden muss.

MittelStack Sortieren

+10

Autos fahren auf einer einspurigen Straße in Richtung Meilenmarke target. Auto i startet an der Meilenmarke position[i] und fährt mit speed[i] Meilen pro Stunde. Kein Auto kann ein anderes überholen: Ein Auto, das auf ein langsameres aufschließt, bleibt direkt dahinter, und von da an fahren beide gemeinsam mit der niedrigeren Geschwindigkeit als eine Kolonne.

Auch ein einzelnes Auto ist eine Kolonne, und ein Auto, das genau am Ziel zu einer Kolonne aufschließt, schließt sich ihr an. Gib die Anzahl der Kolonnen zurück, die am Ziel ankommen.

Funktion

carFleet(target: integer, position: integer-array, speed: integer-array) → integer

targetinteger: die Meile, auf die jedes Auto zufährt
positioninteger-array: die Startmeile jedes Autos
speedinteger-array: die Geschwindigkeit jedes Autos in Meilen pro Stunde
Gibt zurückinteger: die Anzahl der Flotten, die das Ziel erreichen

Einschränkungen

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
Alle Positionen sind unterschiedlich.

Beispiele

Eingabe: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
Ausgabe: 2
Erklärung: Allein benötigen die Autos bei Meile 17, 14, 8 und 2 jeweils 3, 2, 3 und 3 Stunden. Daher holt das Auto bei Meile 14 das bei Meile 17 ein, und die beiden anderen erreichen sie bei Meile 20. Das Auto bei Meile 0 benötigt 10 Stunden und kommt allein an.

Eingabe: target = 9position = [0, 4, 7]speed = [1, 2, 3]
Ausgabe: 3
Erklärung: Die Autos bei den Meilen 7, 4 und 0 benötigen 2/3, 5/2 und 9 Stunden. Jedes würde nach dem Auto vor ihm ankommen, daher holt niemand jemanden ein: 3 Flotten.

Weiterführende Frage

Die Positionen sind ganze Zahlen unterhalb von target. Kannst du die Flotten in O(n + target) Zeit zählen, ohne einen vergleichsbasierten Sortieralgorithmus zu verwenden?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Auf einer Spur ändern die Autos nie ihre Reihenfolge, und entscheidend ist, wann jedes Auto allein ankommen würde: (target - position[i]) / speed[i]. Betrachte die Autos vom nächstgelegenen Ziel aus rückwärts. Ein Auto bildet nur dann eine neue Fahrzeuggruppe, wenn es strikt später ankommen würde als die Fahrzeuggruppe vor ihm.

Überprüfe jedes Auto vor dir

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Ein Auto führt eine Fahrzeugkolonne genau dann an, wenn jedes Auto vor ihm allein strikt früher ankommen würde. Wenn ein Auto vor ihm nicht früher ankommen würde, holt dein Auto es oder seine Kolonne bis zum Ziel ein. Wenn alle früher ankommen, kann nichts vor ihm es aufhalten, denn eine Kolonne kommt zum spätesten Einzelankunftszeitpunkt ihrer Autos an. Zähle die führenden Autos, indem du die Zeiten durch Kreuzmultiplikation exakt vergleichst.

Jedes Auto überprüft alle n Autos: 10^8 Prüfungen für n = 10^4.

Algorithmus

Setze fleets = 0.
Betrachte für jedes Auto i jedes Auto j mit position[j] > position[i].
Wenn es ein j gibt, für das (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j] gilt, wird Auto i eingeholt: Überspringe es.
Andernfalls führt Auto i eine Flotte an: Erhöhe fleets um 1.
Gib fleets zurück.

def carFleet(target, position, speed):
    n = len(position)
    fleets = 0
    for i in range(n):
        dist = target - position[i]
        caught = False
        for j in range(n):
            # Car j is ahead and would not arrive before car i: car i catches it.
            # (target - position[j]) / speed[j] >= dist / speed[i], without division.
            if position[j] > position[i] and (target - position[j]) * speed[i] >= dist * speed[j]:
                caught = True
                break
        if not caught:
            fleets += 1
    return fleets

Nach Position sortieren und die Flotten stapeln

Idee

Nach Position sortiert, wobei das Ziel zuerst kommt, sind die Autos vor dem aktuellen genau die, die bereits gesehen wurden und sich bereits in Kolonnen befinden. Lege die Kolonnen auf einen Stapel; jede wird als Entfernung und Geschwindigkeit ihres vordersten Autos gespeichert, die die Ankunftszeit der Kolonne bestimmen.

Nur das oberste Element ist wichtig. Jede hinzugefügte Kolonne kommt strikt später an als die Kolonne darunter, daher steigen die Zeiten von unten nach oben, und eine Zeit, die später als die des obersten Elements ist, ist später als die jedes vorausfahrenden Autos.

Beispiel 1: In der Reihenfolge sind die Autos bei 17, 14, 8, 2 und 0, mit Entfernung durch Geschwindigkeit 3/1, 6/3, 12/4, 18/6, 20/2. Füge (3, 1) hinzu. Das Auto bei 14 schließt sich an, da 6 × 1 > 3 × 3 falsch ist. Das Auto bei 8 kommt gleichzeitig an, 12 × 1 = 3 × 4, und schließt sich an; ebenso das Auto bei 2. Für das Auto bei 0 gilt 20 × 1 > 3 × 2: hinzufügen.

Algorithmus

Sortiere die Indizes der Autos nach ihrer Position, beginnend mit der größten.
Beginne mit einem leeren Stapel von Flotten.
Berechne für jedes Auto dist = target - position[i].
Wenn der Stapel leer ist oder dist × topSpeed > topDist × speed[i], füge (dist, speed[i]) hinzu; andernfalls schließt sich das Auto der obersten Flotte an.
Gib die Größe des Stapels zurück.

def carFleet(target, position, speed):
    # Visit the cars from the one closest to the target backward.
    order = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
    # One entry per fleet: (distance, speed) of the car at its front, which sets its arrival time.
    stack = []
    for i in order:
        dist, spd = target - position[i], speed[i]
        # dist / spd > top_dist / top_spd, compared without division:
        # this car arrives after the fleet ahead, so it never catches it.
        if not stack or dist * stack[-1][1] > stack[-1][0] * spd:
            stack.append((dist, spd))
    return len(stack)

Stolperfallen und Grenzfälle

Ein exaktes Gleichauf als neue Flotte zählen. Die Autos bei Meile 8 und 2 in Beispiel 1 treffen bei Meile 20 auf die Flotte und schließen sich ihr an. Nur dann hinzufügen, wenn die Zeit strikt später ist.
Überlauf beim Kreuzprodukt. 10^6 × 10^6 = 10^12 passt nicht in 32 Bit: In Java, C, C++, C# und Rust vor der Multiplikation auf 64 Bit erweitern; in R Doubles verwenden.
In die falsche Richtung sortieren. Wenn man beim Auto beginnt, das am weitesten vom Ziel entfernt ist, vergleicht man jedes Auto mit den Autos hinter ihm, die es niemals aufhalten können.
position allein sortieren. Indizes oder (position, speed)-Paare sortieren, damit jede Geschwindigkeit bei ihrem Auto bleibt.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Car Fleet?

Das Sortieren nach Position benötigt O(n log n) und der Durchlauf mit einem Stack benötigt O(n), daher beträgt der Gesamtaufwand O(n log n) Zeit und O(n) Speicher. Jedes Auto mit jedem vorausfahrenden Auto zu vergleichen, benötigt O(n²).

Warum verwendet Car Fleet einen Stack?

Wenn die Autos von vorne betrachtet werden, muss jedes neue Auto nur mit der Flotte direkt davor verglichen werden, also mit der zuletzt gebildeten. Ein Stapel hält diese Flotte ganz oben. Da nur das oberste Element gelesen wird, reichen auch zwei Variablen; der Stapel liefert dir außerdem die Flotten selbst.

Wie vergleichst du Ankunftszeiten ohne Gleitkommazahlen?

Die Ankunftszeit beträgt dist / speed. Da die Geschwindigkeiten positiv sind, gilt d1 / s1 > d2 / s2 genau dann, wenn d1 × s2 > d2 × s1. Beide Seiten sind ganze Zahlen bis zu 10^12, daher berechne sie mit einem 64-Bit-Typ und der Vergleich ist exakt, sodass keine Rundung berücksichtigt werden muss.

def carFleet(target, position, speed):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

target = 20
position = [14, 2, 8, 17, 0]
speed = [3, 6, 4, 1, 2]

Erwartete Ausgabe