Richest Customer Wealth
銀行は、accountsというグリッドを管理しています。このグリッドは、顧客ごとに1行ずつのm行と、銀行ごとに1列ずつのn列で構成されています。accounts[i][j]は、顧客iが銀行jに預けている金額です。顧客の資産は、その顧客の行の合計です。最も資産の多い顧客の資産を返してください。
関数
- accountsinteger-2d-array
- 顧客ごとに1行、銀行ごとに1列の残高のグリッド
- 戻り値integer
- 最大の行合計
制約
1 ≤ accounts.length ≤ 1001 ≤ accounts[i].length ≤ 100であり、すべての行の長さは同じです。0 ≤ accounts[i][j] ≤ 104
例
- 入力
- accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
- 出力
- 14
- 説明
- 各行の合計は
2 + 8 + 1 = 11、5 + 5 + 4 = 14、7 + 0 + 3 = 10です。中央の顧客が最も多く、14です。単一の残高として最も大きい8は、別の人のものですが。
- 入力
- accounts = [[3], [9], [4]]
- 出力
- 9
- 説明
- 各顧客は1つの銀行を利用するため、合計は
3、9、4となり、答えは9です。
提出時に隠しテスト+14件
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
1人の顧客に属する数値は、グリッドの行ですか、それとも列ですか？
各行の値を合計して、1人の顧客の資産を求めます。同時に2行を扱う必要はありません。
これまでの最大合計を保持する変数を1つ用意します。1行の合計を計算して比較し、次の行に進みます。
解説
各残高は必ず1人の顧客に属するため、グリッド全体を読み取る必要があります。どの方法でも時間計算量は O(m × n) を下回りません。読み取りながらどれだけ情報を保持するかが選択のポイントです。すべての合計をリストにすることもできますが、その時点までに見つかった最大の合計だけが重要なので、数値1つで十分です。
すべての合計を列挙し、次に最大のものを選びます
考え方
作業を2つに分けます。まず各行を順に見て、残高を合計し、顧客ごとに合計を1つ保存します。最初の例では、[11, 14, 10]となります。次に、そのリストを調べて最大値の14を見つけます。
処理自体は問題ありません。m × n個の残高をそれぞれ1回ずつ加算し、2回目の走査ではm個の合計を読み取ります。100 × 100のグリッドなら、加算は10^4回です。コストとなるのはリストそのものです。m個の余分な数値を保持し、そのうち1つ以外をすべて捨てることになります。
アルゴリズム
- 空のリスト
totalsを作成します。 - 各行について、残高を合計し、その合計を
totalsに追加します。 richestを最初の合計値に設定します。richestをそれより大きい合計値で置き換え、その後に返します。
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最大値を更新し続ける
考え方
ある行の合計がわかったら、それまでの最大の合計を上回るかどうかを確認するだけです。そこで、すぐに比較して、richest という数値を1つ保持します。最初の例では、richest は 0 → 11 → 14 と変化し、最後の行の合計が 10 になると 14 のままです。
richest は 0 から始めます。残高が負になることはないため、これは安全です。すべての合計は少なくとも 0 であり、すべてゼロのグリッドに対しても正しく 0 を返します。残高が負になる可能性がある場合は、最初の行の合計から始めます。
合計の最大値は 100 × 10^4 = 10^6 なので、32ビット整数ですべての合計を保持できます。
アルゴリズム
richestを0に設定します。- 各行について、残高を合計して
wealthに代入します。 wealth > richestの場合、richestをwealthに設定します。- 最後の行の後、
richestを返します。
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
落とし穴と境界ケース
ループ自体は短いものです。バグは、顧客をどの方向に処理するかを取り違えることで起こります。
- 行ではなく列を合計する。列は、すべての顧客にわたる1つの銀行を表します。その合計では、別の問いへの答えになります。最初の例では、列の合計は
14、13、8となり、最初の列だけがたまたま正解と一致します。 - 最も大きい単一の残高を返す。最初のグリッドで最も大きい数は
8ですが、その所有者の合計は11で、残高が5を超える銀行を持たない顧客の14より少なくなります。 - 行の合計を誤った位置でリセットする。内側のループの前、行のループ内で
wealthを0に設定します。これをループの外で一度だけ設定すると、各顧客が前の顧客のお金を引き継いでしまいます。
よくある質問3
Richest Customer Wealth の時間計算量はどれくらいですか？
O(m × n)（m 人の顧客と n 行の銀行の場合）。すべての残高を一度ずつ加算するためです。スキップできるセルはありません。スキップした残高が、その持ち主を最も裕福にする残高である可能性があるためです。実行中の最大値の計算には、追加で O(1) の領域を使用します。
2次元配列の行の合計の最大値を求めるにはどうすればよいですか？
各行をループしてそれぞれ合計し、最大の合計を変数に保持します。多くの言語では、Python の max(sum(row) for row in accounts) のように、組み込みの sum を使って内側のループを短くできます。どちらの方法でも、各セルを一度ずつ読み取ります。
合計が32ビット整数の範囲を超えることはありますか？
ここでは違います。1行には最大でも100個の残高があり、それぞれ最大でも10^4なので、合計は最大でも10^6となり、2^31 - 1を大幅に下回ります。制限がもっと大きい場合は、64ビット整数に加算します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def maximumWealth(accounts):
# ここにコードを書いてくださいケース1
ケース2
入力
accounts = [[2, 8, 1], [5, 5, 4], [7, 0, 3]]
期待値
14