Pythonで2次元配列からk番目に小さい要素を求めるプログラム

n×n のユーザー入力による整数行列と値 k が与えられたとき、その2次元配列の中から「k番目に小さい要素」を見つけるのが本記事の目的です。この問題は、Python標準ライブラリの heapq モジュールを使うことで効率的に解決できます。

heapqモジュールとは

heapq（ヒープキュー）は、Pythonでヒープ構造（優先度付きキュー）を扱うためのモジュールです。このモジュールの特徴は、毎回ヒープの中で最も小さい要素が取り出される「最小ヒープ（min heap）」として動作する点にあります。また、nsmallest() メソッドを使うことで、データ集合の中から最小のn個の値を簡単に取得することができます。

実行例

入力配列：
10 20 20 40 
15 45 40 30 
32 33 30 50 
12 78 99 78 
k の値：10
10番目に小さい要素は 40

アルゴリズム

処理の手順は以下の通りです。

1. まず2次元配列を作成します。
2. 1行目を変数に代入し、それを最小ヒープに変換します。
3. 残りの行を走査しながら、各要素を最小ヒープにプッシュしていきます。
4. heapqモジュールの nsmallest(k, iterable) メソッドを使い、最初のk個の最小要素のリストを取得します。このリストの最後の要素を出力すれば、それがk番目に小さい要素となります。

サンプルコード

# Pythonプログラム：2次元配列からK番目に小さい要素を求める
import heapq

def smallestele(A):
   assignval = A[0]
   heapq.heapify(assignval)

   for i in A[1:]:
      for j in i:
         heapq.heappush(assignval, j)
   mini = heapq.nsmallest(k, assignval)
   print(k, "番目に小さい要素は", mini[-1])

# ドライバープログラム
if __name__ == "__main__":
   A = []
n = int(input("N x N 行列の N を入力してください : "))
# 2次元配列を格納するためリストを使用
print("要素を入力してください ::>")
for i in range(n):
   row = []                                # 行を一時的に保存するリスト
   for j in range(n):
      row.append(int(input()))             # 入力を行リストに追加
   A.append(row)                           # 行を全体のリストに追加

print(A)
# [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

# 2次元配列を行列形式で表示
print("行列形式で配列を表示")
for i in range(n):
   for j in range(n):
      print(A[i][j], end=" ")
   print()                                 # 改行
k = int(input("k番目の位置を入力してください ::>"))
smallestele(A)

実行結果

Enter N for N x N matrix : 4
Enter the element ::>
10
20
20
40
15
45
40
30
32
33
30
50
12
78
99
78
[[10, 20, 20, 40], [15, 45, 40, 30], [32, 33, 30, 50], [12, 78, 99, 78]]
Display Array In Matrix Form
10 20 20 40 
15 45 40 30 
32 33 30 50 
12 78 99 78 
Enter the k<sup>th</sup> position ::>10
10 番目に小さい要素は 40

まとめ

このように、heapqモジュールの heapify()・heappush()・nsmallest() を組み合わせることで、2次元配列全体をソートすることなく、k番目に小さい要素をシンプルなコードで求めることができます。データ量が多い場合でも、ヒープ構造を活用することで効率的な処理が可能になります。