![見出し画像](https://assets.st-note.com/production/uploads/images/112143526/rectangle_large_type_2_c98ca90fcebcb1317a372bab793848f8.png?width=1200)
Photo by
akane_ohashi
【Python】paizaラーニング レベルアップ問題集「k番目に大きな値」を解いてみた
定番アルゴリズムの学習 - 線形探索メニューの最後の問題群を解きました。
関数化した部分のみ掲載します。
2番めに大きな値
最大値(mx1)、2番めに大きな値(mx2)を、リストの最初の要素で初期化
リストの各要素に対して:
要素がmx1より大きければ:
mx1をm2に格下げし、m1を更新する(この順で処理)
要素がmx1より小さく、かつmx2より大きければ:
mx2を更新する
mx2を返す
def secondMax(l: list):
mx1 = l[0]
mx2 = l[0]
for data in l:
if data > mx1:
mx2 = mx1
mx1 = data
elif data > mx2 and data < mx1:
mx2 = data
else:
pass
return mx2
FINAL: k番目に大きな値
仮の最大値mx1を「非常に大きな正の整数」で初期化する
以下の処理をk回繰り返す:
2番めに大きな値mx2を「非常に小さな負の整数」で初期化する
リストの各要素に対して:
要素がmx2より大きく、かつmx1より小さければ、mx2を更新する
仮の最大値mx1をmx2で更新する
mx1を返す(mx2でも同じ)
def kthMax(l: list, k):
"""
リストの中でk番目に大きな値を返す。
リストの中に重複する値はないことが保証されている。
l: list
k: int
"""
mx1 = 2**31
for _ in range(k):
mx2 = -(2**31)
for data in l:
if data > mx2 and data < mx1:
mx2 = data
mx1 = mx2
return mx1
おわりに
この問題集メニューは「線形探索」の学習を目的としているため、最大値を直接求める関数や、ソートを行う関数は封じ手としました。そのため、公式解答例より凝った見た目のコードになっています。
(というか公式の別解でソート使ってるのを見て「これで良いのか…?」と首を傾げてしまいました)
この記事が気に入ったらサポートをしてみませんか?