【Python】paizaラーニング レベルアップ問題集「k番目に大きな値」を解いてみた

定番アルゴリズムの学習 - 線形探索メニューの最後の問題群を解きました。

線形探索メニュー Python3編 | レベルアップ問題集

関数化した部分のみ掲載します。

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

おわりに

この問題集メニューは「線形探索」の学習を目的としているため、最大値を直接求める関数や、ソートを行う関数は封じ手としました。そのため、公式解答例より凝った見た目のコードになっています。

（というか公式の別解でソート使ってるのを見て「これで良いのか…？」と首を傾げてしまいました）