Richest Customer Wealth

Q: Wie hoch ist die Zeitkomplexität von „Richest Customer Wealth“?

O(m × n) für m Kunden und n Banken, da jedes Guthaben einmal addiert wird. Kein Algorithmus kann eine Zelle überspringen, da jedes übersprungene Guthaben dasjenige sein könnte, das seinen Besitzer zum Reichsten macht. Das laufende Maximum benötigt O(1) zusätzlichen Speicherplatz.

Q: Können die Summen einen 32-Bit-Integer überlaufen lassen?

Nicht hier. Eine Zeile hat höchstens 100 Guthaben von jeweils höchstens 10^4 , also beträgt die Summe höchstens 10^6 und liegt damit weit unter 2^31 - 1 . Bei größeren Grenzwerten würde man die Werte zu einer 64-Bit-Ganzzahl addieren.

EinsteigerArrays und Strings

+10

Eine Bank führt ein Raster accounts mit m Zeilen, eine pro Kunde, und n Spalten, eine pro Bank: accounts[i][j] ist das Geld, das Kunde i in Bank j besitzt. Das Vermögen eines Kunden ist die Summe seiner Zeile. Gib das Vermögen des reichsten Kunden zurück.

Funktion

maximumWealth(accounts: integer-2d-array) → integer

accountsinteger-2d-array: das Raster der Kontostände, eine Zeile pro Kunde und eine Spalte pro Bank
Gibt zurückinteger: die größte Zeilensumme

Einschränkungen

1 ≤ accounts.length ≤ 100
1 ≤ accounts[i].length ≤ 100, und jede Zeile hat dieselbe Länge.
0 ≤ accounts[i][j] ≤ 10⁴

Beispiele

Eingabe: accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
Ausgabe: 14
Erklärung: Die Zeilen ergeben zusammen 2 + 8 + 1 = 11, 5 + 5 + 4 = 14 und 7 + 0 + 3 = 10. Der Kunde in der Mitte hat mit 14 den höchsten Gesamtbetrag, obwohl der größte Einzelbetrag, 8, jemand anderem gehört.

Eingabe: accounts = [[3], [9], [4]]
Ausgabe: 9
Erklärung: Jeder Kunde nutzt eine Bank, also lauten die Summen 3, 9 und 4, und die Antwort ist 9.

+14 versteckte Tests beim Einreichen

Lösung

Jeder Kontostand gehört genau einem Kunden, daher musst du das gesamte Raster auslesen: Kein Ansatz ist schneller als O(m × n). Die Frage ist, wie viel du während des Auslesens speicherst. Eine Liste aller Summen funktioniert, aber es zählt nur die bisher größte Summe, daher reicht eine einzige Zahl.

Liste alle Summen auf und wähle dann die größte aus

Idee

Teile die Aufgabe in zwei Schritte auf. Gehe zuerst jede Zeile durch und addiere ihre Guthaben. Speichere dabei eine Summe pro Kunde. Im ersten Beispiel ergibt das [11, 14, 10]. Durchsuche dann diese Liste nach ihrem größten Wert, 14.

Der Aufwand ist in Ordnung: Jedes der m × n Guthaben wird einmal addiert, und beim zweiten Durchgang werden m Summen gelesen. Bei einem 100 × 100-Raster sind das 10^4 Additionen. Der Preis dafür ist die Liste selbst: m zusätzliche Zahlen, die du nur speicherst, um alle bis auf eine wieder zu verwerfen.

Algorithmus

Erstelle eine leere Liste totals.
Addiere für jede Zeile ihre Guthaben und füge die Summe zu totals hinzu.
Setze richest auf den ersten Gesamtbetrag.
Ersetze richest durch jeden größeren Gesamtbetrag und gib ihn dann zurück.

def maximumWealth(accounts):
    # First pass: every customer's total wealth.
    totals = []
    for customer in accounts:
        wealth = 0
        for money in customer:
            wealth += money
        totals.append(wealth)
    # Second pass: the largest total.
    richest = totals[0]
    for wealth in totals:
        if wealth > richest:
            richest = wealth
    return richest

Führe ein laufendes Maximum

Idee

Sobald die Summe einer Zeile bekannt ist, muss nur noch geprüft werden, ob sie die bisher größte Summe übertrifft. Vergleiche sie also sofort und behalte eine Zahl im Blick: richest. Im ersten Beispiel nimmt richest die Werte 0 → 11 → 14 an und bleibt bei 14, wenn die letzte Zeile die Summe 10 ergibt.

Starte richest mit 0. Das ist sicher, weil kein Kontostand negativ ist und daher jede Summe mindestens 0 beträgt; ein Raster aus Nullen gibt korrekterweise 0 zurück. Wenn Kontostände negativ sein könnten, würdest du stattdessen mit der Summe der ersten Zeile beginnen.

Die größtmögliche Summe ist 100 × 10^4 = 10^6, daher kann eine 32-Bit-Ganzzahl jede Summe speichern.

Algorithmus

Setze richest auf 0.
Addiere für jede Zeile ihre Guthaben zu wealth.
Wenn wealth > richest gilt, setze richest auf wealth.
Gib nach der letzten Zeile richest zurück.

def maximumWealth(accounts):
    richest = 0  # money is never negative, so 0 is a safe start
    for customer in accounts:
        richest = max(richest, sum(customer))
    return richest

Stolperfallen und Grenzfälle

Die Schleifen sind kurz. Die Fehler entstehen dadurch, dass man verwechselt, in welcher Richtung die Kundinnen und Kunden durchlaufen werden.

Spalten statt Zeilen summieren. Eine Spalte steht für eine Bank über alle Kundinnen und Kunden hinweg; ihre Summe beantwortet eine andere Frage. Im ersten Beispiel ergeben die Spalten 14, 13 und 8, und nur die erste entspricht zufällig der richtigen Antwort.
Das größte einzelne Guthaben zurückgeben. 8 ist die größte Zahl im ersten Raster, aber die betreffende Person hat insgesamt 11 – weniger als die 14 der Person, die kein Guthaben über 5 hat.
Die Zeilensumme an der falschen Stelle zurücksetzen. Setze wealth innerhalb der Zeilenschleife, vor der inneren Schleife, auf 0. Setzt du den Wert einmal außerhalb zurück, übernimmt jede Kundin und jeder Kunde das Geld der vorherigen Person.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von „Richest Customer Wealth“?

O(m × n) für m Kunden und n Banken, da jedes Guthaben einmal addiert wird. Kein Algorithmus kann eine Zelle überspringen, da jedes übersprungene Guthaben dasjenige sein könnte, das seinen Besitzer zum Reichsten macht. Das laufende Maximum benötigt O(1) zusätzlichen Speicherplatz.

Wie findest du die maximale Zeilensumme eines 2D-Arrays?

Gehe die Zeilen durch, summiere jede einzelne und speichere die größte Summe in einer Variablen. Viele Sprachen verkürzen die innere Schleife mit einer integrierten Summenfunktion, wie etwa max(sum(row) for row in accounts) in Python. In beiden Fällen liest du jede Zelle genau einmal.

Können die Summen einen 32-Bit-Integer überlaufen lassen?

Nicht hier. Eine Zeile hat höchstens 100 Guthaben von jeweils höchstens 10^4, also beträgt die Summe höchstens 10^6 und liegt damit weit unter 2^31 - 1. Bei größeren Grenzwerten würde man die Werte zu einer 64-Bit-Ganzzahl addieren.

Python

def maximumWealth(accounts):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]

Erwartet