Aggressive Cows

Q: Wie hoch ist die Zeitkomplexität von Aggressive Cows?

Das Sortieren benötigt O(n log n) und die binäre Suche O(n log D) , wobei D die Spannweite der Ställe geteilt durch k-1 ist. Abgesehen von einer sortierten Kopie beträgt der Speicherbedarf O(1) .

Q: Warum geht die erste Kuh immer in den Stall ganz links?

Nimm eine beliebige passende Platzierung und stelle ihre linkeste Kuh in den linkesten Stall. Diese Kuh bewegt sich nur von den anderen weg, sodass kein Abstand kleiner wird, und bei einer optimalen Platzierung wird der linkeste Stall genutzt.

Q: Woran erkennst du eine binäre Suche über die Antwort?

Die Frage sucht nach dem größten oder kleinsten Wert, für den etwas möglich ist. Zu prüfen, ob ein einzelner Wert möglich ist, ist viel einfacher, als den besten Wert zu finden, und mit zunehmendem Wert wechseln die Antworten nur einmal. Hier ist der Wert der Abstand, und die Prüfung besteht in der gierigen Platzierung.

MittelBinäre Suche Sortieren Greedy

+10

Ein Stall hat Boxen entlang einer geraden Linie, und stalls[i] ist die Position der Box i. Alle Positionen sind unterschiedlich und in keiner bestimmten Reihenfolge angegeben. Du musst k Kühe in k verschiedene Boxen setzen. Die Kühe kämpfen, wenn sie nahe beieinander stehen. Deshalb möchtest du den Abstand zwischen den zwei nächstgelegenen Kühen so groß wie möglich machen.

Gib den größtmöglichen Wert des kleinsten Abstands zwischen zwei beliebigen Kühen zurück.

Funktion

aggressiveCows(stalls: integer-array, k: integer) → integer

stallsinteger-array: die unterschiedlichen Stallpositionen, in beliebiger Reihenfolge
kinteger: die Anzahl der Kühe, die platziert werden sollen
Gibt zurückinteger: der größtmögliche Mindestabstand zwischen zwei Kühen

Einschränkungen

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
Alle Positionen in stalls sind unterschiedlich.
2 ≤ k ≤ stalls.length

Beispiele

Eingabe: stalls = [10, 1, 7, 4, 15]k = 3
Ausgabe: 6
Erklärung: Die Kühe bei 1, 7 und 15 stehen 6 bzw. 8 voneinander entfernt. Ein Abstand von 7 funktioniert nicht: Nach 1 kommt die nächste Kuh auf 10, und es gibt keinen Stall bei 17 oder weiter.

Weiterführende Frage

Was ändert sich, wenn die Stände im Kreis stehen, sodass der letzte Stand in der Reihenfolge auch ein Nachbar des ersten ist?

Tipps

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

0 von 3 geöffnet

Lösung

Lege einen Abstand fest und frage: Können k Kühe so aufgestellt werden, dass jede zwei mindestens diesen Abstand voneinander haben? Ein Durchlauf mit einem Greedy-Algorithmus über die sortierten Ställe beantwortet die Frage. Mit wachsendem Abstand wechselt die Antwort genau einmal von Ja zu Nein, daher findet die binäre Suche das letzte Ja.

Sortieren und dann jede Lücke der Reihe nach ausprobieren

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

Idee

Sortiere die Positionen. Die beiden nächstgelegenen Kühe sind dann immer Nachbarn, also ist ein Abstand g geeignet, wenn jedes Paar benachbarter Kühe mindestens g auseinandersteht.

Um einen Abstand zu testen, setze eine Kuh in den Stall ganz links und dann jeweils eine in einen Stall, der mindestens g hinter der letzten Kuh liegt. Diese gierige Platzierung bringt so viele Kühe unter wie jede andere Platzierung. Ordne eine beliebige funktionierende Platzierung von links nach rechts: Die Kuh i der gierigen Platzierung steht nie rechts von Kuh i dieser Platzierung, sodass die gierige Platzierung spätestens für ihre nächste Kuh einen Stall findet.

Ein Abstand von 1 funktioniert immer. Probiere also g = 2, 3, ... aus und höre beim ersten Abstand auf, bei dem weniger als k Kühe platziert werden. Im ersten Beispiel platziert Abstand 6 drei Kühe und Abstand 7 nur zwei, also ist die Antwort 6.

Bei zwei Kühen und Ställen an den Positionen 0 und 10^9 sind das ungefähr 10^9 Durchläufe über 5000 Ställe, also 5 × 10^12 Schritte.

Algorithmus

Sortiere die Positionen.
Schreibe die Prüfung für einen Abstand g: eine Kuh bei pos[0], dann eine Kuh in jedem Stall, für den pos[i] - last ≥ g gilt, und zähle die Kühe.
Beginne mit gap = 1.
Solange die Prüfung für gap + 1 mindestens k Kühe platziert, erhöhe gap um 1.
Gib gap zurück.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

Binäre Suche auf der Lücke

Idee

Eine Platzierung, bei der jede Lücke mindestens g+1 beträgt, hat auch bei jeder Lücke mindestens g, daher lauten die Prüfergebnisse ja, ..., ja, nein, ..., nein. Die binäre Suche findet das letzte Ja.

Suche ab lo = 1, was immer funktioniert, bis hi = der Spannweite geteilt durch k-1, abgerundet: k Kühe lassen innerhalb der Spannweite k-1 Lücken, daher kann die kleinste nicht größer sein. Bei einer erfolgreichen Prüfung wird lo = mid gesetzt, also muss mid aufgerundet werden; abgerundet wiederholen sich lo = 5 und hi = 6 endlos.

Im ersten Beispiel beträgt die Spannweite 14 und k = 3, also hi = 7. Lücke 4 besteht die Prüfung, Lücke 6 besteht die Prüfung, Lücke 7 besteht sie nicht, und der Bereich schließt sich bei 6.

Ein Bereich mit einer Breite von bis zu 10^9 schließt sich mit etwa 30 Prüfungen von 5000 Ställen, also ungefähr 150.000 Schritten.

Algorithmus

Sortiere die Positionen.
Setze lo = 1 und hi = (pos[n-1] - pos[0]) / (k-1), abgerundet.
Solange lo < hi, berechne mid = lo + (hi - lo + 1) / 2.
Wenn die Greedy-Prüfung bei mid mindestens k Kühe platziert, setze lo = mid; andernfalls setze hi = mid - 1.
Gib lo zurück.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

Stolperfallen und Grenzfälle

Die Sortierung überspringen. Bei der unsortierten Liste [10, 1, 7, 4, 15] mit Abstand 6 beginnt die Prüfung bei 10, findet keinen späteren Stall, der mindestens 6 davon entfernt ist, und meldet eine Kuh.
mid abrunden, während ein Durchlauf lo = mid setzt. Sobald hi = lo + 1 gilt, verkleinert sich der Bereich nicht mehr und die Schleife endet nie.
Auf genau k Kühe prüfen. Bei Abstand 1 platziert das erste Beispiel 5 Kühe, also mehr als 3, und der Abstand funktioniert trotzdem; prüfe count ≥ k.
Die Kuhanzahl bei 0 beginnen lassen. Die Kuh im ganz linken Stall zählt mit, daher beginnt die Anzahl bei 1.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Aggressive Cows?

Das Sortieren benötigt O(n log n) und die binäre Suche O(n log D), wobei D die Spannweite der Ställe geteilt durch k-1 ist. Abgesehen von einer sortierten Kopie beträgt der Speicherbedarf O(1).

Warum geht die erste Kuh immer in den Stall ganz links?

Nimm eine beliebige passende Platzierung und stelle ihre linkeste Kuh in den linkesten Stall. Diese Kuh bewegt sich nur von den anderen weg, sodass kein Abstand kleiner wird, und bei einer optimalen Platzierung wird der linkeste Stall genutzt.

Woran erkennst du eine binäre Suche über die Antwort?

Die Frage sucht nach dem größten oder kleinsten Wert, für den etwas möglich ist. Zu prüfen, ob ein einzelner Wert möglich ist, ist viel einfacher, als den besten Wert zu finden, und mit zunehmendem Wert wechseln die Antworten nur einmal. Hier ist der Wert der Abstand, und die Prüfung besteht in der gierigen Platzierung.

def aggressiveCows(stalls, k):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

stalls = [10, 1, 7, 4, 15]
k = 3

Erwartete Ausgabe