Chocolate Distribution Problem

Q: Wie hoch ist die zeitliche Komplexität des Problems der Schokoladenverteilung?

Das Sortieren benötigt O(n log n) und das Verschieben des Fensters aus m Paketen benötigt O(n) , also beträgt der Gesamtaufwand O(n log n) . Der zusätzliche Speicherbedarf beträgt O(n) für eine sortierte Kopie oder O(1) zusätzlich zum Sortieren selbst, wenn du die Eingabe direkt sortierst.

Q: Ist das Problem der Schokoladenverteilung ein Sliding-Window-Problem?

Ja, ein Fenster fester Größe über den sortierten Paketen. Anders als bei einem Fenster mit laufender Summe muss beim Verschieben nichts aktualisiert werden: Die Differenz jedes Fensters ergibt sich aus einer einzigen Subtraktion des ersten Pakets vom letzten.

Q: Kann das Problem der Schokoladenverteilung ohne Sortieren gelöst werden?

Die Größen sind hier höchstens 10^5 , daher sortiert ein Zählsortierverfahren sie in O(n + 10^5) Zeit, und dieselbe Folgerung gilt. Bei unbeschränkten Größen können Vergleiche allein O(n log n) nicht unterbieten: Für m = 2 ist die Antwort genau dann 0, wenn zwei Pakete gleich sind, und im schlimmsten Fall sind so viele Vergleiche nötig, um ein Duplikat zu erkennen.

LeichtSortieren Sliding Window

+10

Du hast einige Schokoladenpakete, und packets[i] gibt die Anzahl der Schokoladenstücke im Paket i an. Jede:r von m Schüler:innen erhält genau ein Paket, sodass m verschiedene Pakete ausgegeben werden. Wähle sie so aus, dass die Differenz zwischen dem größten und dem kleinsten ausgegebenen Paket so klein wie möglich ist.

Schreibe eine Funktion namens minDifference, die diese kleinstmögliche Differenz zurückgibt.

Funktion

minDifference(packets: integer-array, m: integer) → integer

packetsinteger-array: die Anzahl der Schokoladenstücke in jeder Packung
minteger: die Anzahl der Schüler, von denen jeder ein Paket erhält
Gibt zurückinteger: die kleinstmögliche Differenz zwischen dem größten und dem kleinsten ausgeteilten Paket

Einschränkungen

2 ≤ m ≤ packets.length ≤ 10⁴
1 ≤ packets[i] ≤ 10⁵
Zwei Packungen können die gleiche Anzahl an Pralinen enthalten.

Beispiele

Eingabe: packets = [9, 3, 15, 7, 11, 4]m = 3
Ausgabe: 4
Erklärung: Sortiert lauten die Pakete 3, 4, 7, 9, 11 und 15. Sowohl 3, 4, 7 als auch 7, 9, 11 ergeben eine Differenz von 4, und keine drei Pakete liegen näher beieinander.

Eingabe: packets = [8, 1, 5]m = 3
Ausgabe: 7
Erklärung: Es gibt drei Schüler und drei Pakete, also wird jedes Paket verteilt und die Differenz beträgt 8 - 1 = 7.

Tipps

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

0 von 3 geöffnet

Lösung

Alle Gruppen aus m Paketen auszuprobieren, ist viel zu langsam. Die beste Auswahl besteht immer aus m Paketen, die nach dem Sortieren nebeneinanderliegen. Sortiere also einmal, und die Antwort ist die kleinste Differenz über ein beliebiges Fenster aus m benachbarten Paketen, die in einem Durchlauf gefunden wird.

Das kleinste Paket reparieren

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

Idee

Lege das kleinste Paket fest, das du verteilst: low. Damit das größte Paket möglichst klein bleibt, nimm die m-1 kleinsten Pakete, die mindestens low enthalten. Die Differenz ist dann das m-kleinste Paket mit mindestens low minus low. Probiere jedes Paket als low aus, überspringe alle, für die es weniger als m Pakete gibt, die mindestens so groß sind, und behalte die kleinste Differenz.

Bei jeder der n Möglichkeiten werden bis zu n Pakete gefiltert und sortiert: O(n² log n). Bei n = 10^4 unterschiedlichen Größen führen allein die Sortierungen zu etwa 6 × 10^8 Vergleichen.

Algorithmus

Setze best auf einen Wert, den keine Antwort überschreiten kann.
Sammle für jedes Paket low alle Pakete mit mindestens low Schokoladen und sortiere sie.
Wenn es mindestens m davon gibt, ist das m-kleinste minus low ein Kandidat.
Behalte den kleinsten Kandidaten in best und gib ihn zurück.

def minDifference(packets, m):
    best = max(packets) - min(packets)  # no gap can be wider than this
    for low in packets:
        # The packets that could go out alongside low, smallest first (low is one of them).
        bigger = sorted(x for x in packets if x >= low)
        if len(bigger) >= m:
            best = min(best, bigger[m - 1] - low)
    return best

Sortiere und verschiebe ein Fenster aus m Paketen

Idee

In aufsteigender Reihenfolge hat ein Fenster sizes[i..i+m-1] das kleinste Paket zuerst und das größte zuletzt, daher ist seine Differenz sizes[i+m-1] - sizes[i].

Eine beste Auswahl kann immer ein Fenster sein. Wenn bei einer Auswahl ein Paket übersprungen wird, das zwischen dem kleinsten und dem größten liegt, tausche das größte gegen dieses Paket aus. Das kleinste bleibt gleich und das größte kann nur kleiner werden, daher wächst die Differenz nie. Wiederhole dies, bis keine Lücke mehr bleibt.

Im ersten Beispiel ergeben die Fenster der Größe drei die Werte 4, 5, 4 und 6, also ist die Antwort 4. Das Sortieren kostet O(n log n) und das Verschieben des Fensters O(n).

Algorithmus

Sortiere die Päckchen aufsteigend in sizes.
Setze best auf sizes[m-1] - sizes[0], das erste Fenster.
Vergleiche für jeden Startwert i von 1 bis n-m sizes[i+m-1] - sizes[i] mit best und behalte den kleineren Wert.
Gib best zurück.

def minDifference(packets, m):
    sizes = sorted(packets)
    best = sizes[m - 1] - sizes[0]
    # The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
    for i in range(1, len(sizes) - m + 1):
        best = min(best, sizes[i + m - 1] - sizes[i])
    return best

Stolperfallen und Grenzfälle

Das Fenster bei i+m statt bei i+m-1 enden lassen, wodurch m+1 Päckchen gemessen werden.
Eine Iteration zu früh aufhören. Die Startwerte reichen von 0 bis einschließlich n-m. Bei [1, 10, 20, 21] mit m = 2 überspringt eine Schleife mit i < n-m den einzigen Unterschied von 1.
Das Sortieren überspringen. Bei [9, 3, 15, 7, 11, 4] unterscheiden sich die ersten drei Päckchen um 12, während die Antwort 4 ist.
Nur das erste Fenster messen. Die m kleinsten Päckchen sind eine Möglichkeit, aber die beste Gruppe kann an jeder Stelle beginnen.
Zahlen als Text sortieren. In JavaScript setzt sort() ohne Vergleichsfunktion 100000 vor 9.

Häufige Fragen3

Wie hoch ist die zeitliche Komplexität des Problems der Schokoladenverteilung?

Das Sortieren benötigt O(n log n) und das Verschieben des Fensters aus m Paketen benötigt O(n), also beträgt der Gesamtaufwand O(n log n). Der zusätzliche Speicherbedarf beträgt O(n) für eine sortierte Kopie oder O(1) zusätzlich zum Sortieren selbst, wenn du die Eingabe direkt sortierst.

Ist das Problem der Schokoladenverteilung ein Sliding-Window-Problem?

Ja, ein Fenster fester Größe über den sortierten Paketen. Anders als bei einem Fenster mit laufender Summe muss beim Verschieben nichts aktualisiert werden: Die Differenz jedes Fensters ergibt sich aus einer einzigen Subtraktion des ersten Pakets vom letzten.

Kann das Problem der Schokoladenverteilung ohne Sortieren gelöst werden?

Die Größen sind hier höchstens 10^5, daher sortiert ein Zählsortierverfahren sie in O(n + 10^5) Zeit, und dieselbe Folgerung gilt. Bei unbeschränkten Größen können Vergleiche allein O(n log n) nicht unterbieten: Für m = 2 ist die Antwort genau dann 0, wenn zwei Pakete gleich sind, und im schlimmsten Fall sind so viele Vergleiche nötig, um ein Duplikat zu erkennen.

def minDifference(packets, m):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

packets = [9, 3, 15, 7, 11, 4]
m = 3

Erwartete Ausgabe