Pythonでサイズkの辞書式に最小の部分列を見つけるプログラム

問題の概要

数値のリスト nums と整数 k が与えられたとき、サイズがちょうど k となる「辞書式順序で最小」の部分列（サブシーケンス）を求めることを考えます。ここで部分列とは、元のリストから要素を選び、元の順序を保ったまま並べたものを指します。

例として、nums = [2, 3, 1, 10, 3, 4]、k = 3 の場合を考えてみましょう。このとき出力は [1, 3, 4] となります。サイズ3の部分列の中で、この並びが最も辞書式に小さいためです。

解法のアプローチ

この問題は貪欲法（グリーディ法）で解くことができます。手順は以下のとおりです。

• 最初の要素は、リストの先頭から n−k 番目までの範囲で自由に選べます（その後に残り k−1 個を配置する余地が必要なため）。
• この範囲内で最小値を選びます。同じ値が複数ある場合は、できるだけ後ろ側にあるものを採用すると、以降の選択肢が広がります。
• 選んだ位置より後ろに対して、同じ手順を繰り返します。
• これを k 回繰り返し、選んだ要素を順につなげたものが答えになります。

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

class Solution:
    def solve(self, nums, k):
        l, r = len(nums), k - 1
        out = []
        for j in range(k):
            mn = nums[~r]
            for i in range(r, l):
                if mn >= nums[~i]:
                    mn = nums[~i]
                    l = i
            r -= 1
        out.append(mn)
    return out

ob = Solution()
nums = [2, 3, 1, 10, 3, 4]
k = 3
print(ob.solve(nums, k))

入力

[2, 3, 1, 10, 3, 4], 3

出力

[1, 3, 4]

コードのポイント

この実装では、ビット反転演算子 ~ を使ってリストの後ろ側へアクセスしています。Pythonでは ~i は -i-1 と等しいため、nums[~i] は「後ろから i+1 番目の要素」を意味します。これにより、末尾基準のインデックス計算を簡潔に記述できます。

変数 r は「まだ選ぶ必要がある残りの要素数 − 1」を表し、各ステップにおける探索範囲の制御に使われます。比較条件を >= としているのは、同じ最小値が見つかったときに、より後ろの位置を採用するためです。こうすることで、次の要素を選ぶ際の候補範囲を最大限に確保できます。

なお、この手法の計算量は O(n×k) です。要素数が非常に多い場合は、単調スタックを利用することで O(n) まで計算量を抑えられるため、大規模な入力が想定される場面ではスタックを使った実装も検討するとよいでしょう。