Pythonでソート済み行列からn番目に小さい数を見つける方法

問題の概要

行と列がそれぞれ非減少順（昇順）にソートされた2次元行列が与えられたとき、その中からn番目に小さい数を見つけることを考えます。

例えば、次のような行列が入力されたとします。

このとき n = 4 とすると、出力は 6 になります。

解法のアプローチ

最もシンプルで分かりやすい方法は、行列内のすべての要素を1つのリストに集め、ソートしてからn番目の要素を取り出すことです。手順は以下の通りです。

• 空のリスト lst を用意する
• 行列の各行 i について、その中の各要素 j を lst の末尾に追加していく
• リスト lst をソートする
• lst[n] を返す

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, matrix, n):
        lst = []
        for i in matrix:
            for j in i:
                lst.append(j)
        lst.sort()
        return lst[n]

ob = Solution()
matrix = [[2, 4, 30], [3, 4, 31], [6, 6, 32]]
n = 4
print(ob.solve(matrix, n))

入力

matrix = [
    [2, 4, 30],
    [3, 4, 31],
    [6, 6, 32]
]
n = 4

出力

6

よりPythonicな書き方

itertools.chain を使うと、ネストしたループを一行でまとめて書くことができます。

from itertools import chain

class Solution:
    def solve(self, matrix, n):
        return sorted(chain.from_iterable(matrix))[n]

計算量と効率化のポイント

上記の方法では、行数を m、列数を k とすると、全要素の収集に O(mk)、ソートに O(mk log(mk)) の時間計算量が必要です。データ量が少ない場合は十分実用的ですが、大規模な行列では以下のような代替手段が有効です。

• ヒープを使う方法： heapq モジュールで各行の先頭要素を管理し、最小値をn回取り出すことで O(n log m) で求められます。
• 二分探索を使う方法： 行・列がソートされている性質を活かし、「mid 以下の要素数」を数えながら値の範囲を絞り込むことで、O((m + k) log(最大値 − 最小値)) 程度まで高速化できます。

まずは本記事のシンプルな実装でロジックを理解し、必要に応じて効率的なアルゴリズムへ発展させるのがおすすめです。