配列の最大と最小
2 周まわすのは、もったいない
気温の記録から「いちばん低かった日」と「いちばん高かった日」を出したいとします。素直に書けば、低いほうを探すために 1 周、高いほうを探すためにもう 1 周、合わせて 2 周です。答えは出ますが、同じデータを 2 回読んでいます。
読み込みが重いときや、値が次々と流れてくるときには、この 2 周目が取れません。1 周のあいだに 2 つを同時に追えれば、データに触るのは 1 回で済みます。
1 周のあいだに、2 つのことをやる
同時に追うというのは、難しい話ではありません。追いたいものの数だけ変数を用意して、ループの中でどちらも更新するだけです。合計と件数を同時に持って平均を出す例で見てみます。
Python
names = ["さとう", "たかはし", "あべ"]
total = 0
count = 0
for n in names:
total += len(n)
count += 1
print(total / count) # 3.0ループは 1 つ、更新する変数は 2 つ。片方が合計を、もう片方が件数を覚えています。低いほうと高いほうも、これと同じ形で並べられます。
候補を 1 つ持って、勝ったら差し替える
いちばん低い値やいちばん高い値は、「今のところの一番」を変数に持ち、より良いものが来たら差し替える、というやり方で求めます。形はこうです。
Python
best = "たかはし"
challenger = "さとう"
if len(challenger) > len(best):
best = challenger
print(best) # たかはし気温 12, 19, 7, 15, 9 を左から見たとき、2 つの暫定値は次のように動きます。
| 見た値 | 暫定の最低 | 暫定の最高 |
|---|---|---|
| 12 | 12 | 12 |
| 19 | 12 | 19 |
| 7 | 7 | 19 |
| 15 | 7 | 19 |
| 9 | 7 | 19 |
最初の 1 件では、最低も最高も同じ値です。あとは差し替えが起きるかどうかだけで、1 件につき比較は 2 回。全体でおよそ 2n 回、オーダーは O(n) です。覚えておく変数は 2 つだけなので、使うメモリは件数によらず一定、つまり O(1) です。
0 から始めると、答えがずれる
暫定値を 0 で始めるのは、よくある事故です。気温がすべて氷点より上の日ばかりなら、最低はいつまでも 0 のまま。逆にすべて氷点下なら、最高が 0 のまま。存在しない値を答えとして返してしまううえ、たまたま 0 をまたぐデータではテストが通ってしまうので、余計に厄介です。
暫定値は必ず 実際のデータの 1 件目 から始めてください。そうすれば、値がどんな範囲でも正しく動きます。
ただし、1 件目が取れない場合があります。
Python
temps = []
print(temps[0])
# IndexError: list index out of range空のデータが来ないと決まっているなら、そのまま進めて構いません。決まっていないなら、本体に入る前に弾いておきます。
要件
- 1 回のループで最小値と最大値の両方を求めること
- 組み込みの min() / max() / Math.min / Math.max は使わない
- 戻り値は [min, max] の順の長さ 2 の配列
入出力例
minMax([3,1,4,1,5,9,2,6]) → [1,9]
minMax([42]) → [42,42]
minMax([7,7,7]) → [7,7]
minMax([-5,-10,-3]) → [-10,-3]
minMax([1,2,3,4,5]) → [1,5]
minMax([5,4,3,2,1]) → [1,5]ヒント
