Find the Largest Number
空でない整数のリスト nums が与えられます。その中の最大値を返してください。値は負になることもあるため、答えも負になる場合があります。max のような組み込みの最大値関数を使わず、自分で比較して求めてください。
関数
- numsinteger-array
- 検索する整数のリスト
- 戻り値integer
- nums の中で最も大きい値
制約
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
例
- 入力
- nums = [3, 17, 4, 12, 9]
- 出力
- 17
- 説明
- 左から読み進めると、その時点での最大値は
3、次に17です。4、12、9はどれも17を上回らないため、答えは17です。
- 入力
- nums = [-8, -3, -11, -3]
- 出力
- -3
- 説明
- すべての値は負で、
-3がゼロに最も近いため、最大です。これは2回現れますが、返すのは位置ではなく値です。
- 入力
- nums = [42]
- 出力
- 42
- 説明
- 値が1つのリストでは、その値が最大値です。
提出時に隠しテスト+13件
発展問題
まず値をペアごとに比較することで、2n回ではなく約3n/2回の比較で最大値と最小値の両方を返せますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
値を一つずつ読み取ります。すでに見た値について、覚えておく必要があることは何ですか？
これまでの最大値だけを覚えておきます。新しい値は、それを上回るか、上回らないかのどちらかです。
すべての値が負の数である可能性があるため、実行中の最大値は
0ではなくnums[0]から始めます。それを各値と比較し、大きい方を保持します。
解説
読み飛ばした値が最大値である可能性があるため、どの解法でもすべての要素を少なくとも1回は読み取ります。実際に決めることは、現在の最大値をどこから始めるかです。リスト内の値がすべて負である可能性があるため、0ではなく最初の要素から始めます。
コピーを並べ替えて最後の値を取得する
考え方
小さい値から大きい値へと並べ替えられたリストでは、最大値は末尾にあります。呼び出し元のリストをそのままに保つため、numsをコピーし、そのコピーを並べ替えて、最後の要素を返します。[3, 17, 4, 12, 9]の場合、並べ替えたコピーは[3, 4, 9, 12, 17]で、最後の要素は17です。
答えは正しいですが、並べ替えは必要以上の処理を行います。すべての値を順番に並べるため、およそn log n回の比較が必要です。n = 5000の場合は約60,000回になりますが、必要なのは最大値だけです。コピーにもO(n)のメモリが必要です。
JavaScriptとTypeScriptでは、sortに比較関数を渡します。比較関数を渡さないと、数値を文字列として比較するため、12と17が3より前に並びます。
アルゴリズム
numsをコピーします。- 数値を数値として比較しながら、コピーを小さい順に並べ替えます。
- 並べ替えたコピーの最後の要素を返します。
def findMax(nums):
ordered = sorted(nums) # a sorted copy, smallest first
return ordered[-1]現在までの最大値を追跡する1回の走査
考え方
これまでに見つかった最大の値を保持するために、largestという変数を1つ用意します。これをnums[0]で初期化し、すべての値と比較して、より大きい値があればその都度置き換えます。ループが終わると、largestはすべての要素と比較されているため、リスト内にこれを上回る値はありません。
[3, 17, 4, 12, 9]の場合、largestは3から始まり、17になった後、4、12、9を見ても17のままです。これは有効な比較がn-1回で、追加の変数が1つということです。
nums[0]から始めることで、負の数だけのリストにも対応できます。代わりに0から始めると、[-8, -3, -11, -3]のどの値もそれを上回らないため、リストにさえ含まれていない値である0を返してしまいます。
アルゴリズム
largestをnums[0]に設定します。nums内のすべての値xを順に処理します。x > largestの場合、largestをxに設定します。- ループの後、
largestを返します。
def findMax(nums):
largest = nums[0] # never 0: every value may be negative
for x in nums:
if x > largest:
largest = x
return largest
落とし穴と境界ケース
ループは短いので、間違いは開始位置と読み取る内容にあります。
largestを0または-1から始める。値がすべてその開始値より小さいリストでは、リストに含まれない数が返されます。-1000000のような適当に決めた小さな数から始める。この例の値は-10^9まで小さくなるため、開始値が依然として最大値になります。nums[0]なら推測する必要はありません。- 最初の要素が
nums[1]であるLuaやRで、nums[0]を読み取る。Luaではnilが返され、Rでは空のベクトルが返されます。 - インデックスが0始まりの言語で
i ≤ nを使ってループし、末尾を越えた要素を読み取る。 - JavaScriptやTypeScriptで数値比較関数を指定せずにソートする。
[3, 17, 4, 12, 9]は文字列としての順序では9が最後になるため、17ではなく9が返されます。
よくある質問4
配列内の最大値を見つける時間計算量はどのくらいですか？
1回の走査にかかる時間は O(n)、追加の空間計算量は O(1) です。ソートされていない配列では、これより効率のよい方法はありません。読み取らなかった要素が最大値である可能性があるためです。先にソートすると O(n log n) かかり、何の利点もないのに処理が遅くなります。
maxを使わずに、配列の中で最も大きい数を見つけるにはどうすればよいですか？
最初の要素を変数に格納します。残りの要素をループし、変数の値より大きい要素があれば、その要素を代わりに格納します。ループが終了すると、変数には最大の値が格納されています。
なぜ最大値は0ではなく、最初の要素から始めるべきなのでしょうか？
すべての値が負の場合、0より大きい値はないため、0で初期化された最大値は変わらず、関数は0を返します。最初の要素は常に実際の候補なので、そこから始めるのはどのようなリストでも正しい方法です。リストが空でない限り、使用する言語の最小の整数を使う方法もあります。
並べ替えは、最大値を見つけるのにどのような場合に適していますか？
最大値だけでなく、たとえば上位3つの値や中央値が必要で、同じリストについてこのような質問を何度もする場合です。最大値を1つだけ求めるなら、1回の走査のほうが速く、リストも変更されません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def findMax(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [3, 17, 4, 12, 9]
期待値
17