【Python】行・列ソート済み行列に含まれる負の数を効率的にカウントする方法

この記事では、行方向・列方向にソートされた行列（row-wise and column-wise sorted matrix）に含まれる負の数を、計算量の少ない最適なアルゴリズムでカウントするPythonプログラムを紹介します。

行・列ソート済み行列とは

「行・列ソート済み配列」とは、任意の位置にある値が、同じ行の右隣の値、および同じ列の下の値と比較して小さいか等しい（昇順になっている）行列のことです。つまり、左から右へ、上から下へと向かって値が増えていく構造を持っています。

例：行列Mの場合

M = [[-40, -12,  1,  5],
     [-35,  -2,  5, 15],
     [-22,  -1, 13, 18],
     [-12,   0, 15, 38]]

この行列Mでは、1行目の先頭の要素である-40は、同じ行の次の列の値である-12よりも小さく、さらに同じ列の次の行の値である-35よりも小さくなっています。以下同様に、すべての行・列が昇順にソートされています。

Pythonでの実装例

# 行列は昇順にソートされている必要があります。
# ソートされていない場合、このアルゴリズムは正しく動作しません。
matrix = [
    [-40, -12,  1,  5],
    [-35,  -2,  5, 15],
    [-22,  -1, 13, 18],
    [-12,   0, 15, 38]
]

# 行数と列数を取得
row_count = len(matrix)
column_count = len(matrix[0])

# 右上の角から探索を開始
a = 0                    # 現在の行インデックス
b = column_count - 1     # 現在の列インデックス
count_of_negative_integer = 0

while a < row_count and b >= 0:
    if matrix[a][b] < 0:
        # 行が昇順ソートされているため、
        # この位置より左側の要素はすべて負の数
        count_of_negative_integer += (b + 1)
        a += 1           # 次の行へ移動
    else:
        b -= 1           # 0以上なら左へ移動

print("ソート済み行列に含まれる負の整数の個数:", count_of_negative_integer)

実行結果

ソート済み行列に含まれる負の整数の個数: 7

プログラムの仕組み

• 右上からスタート： 探索は行列の右上隅（0行目の最終列）から始めます。ここがこのアルゴリズム最大のポイントです。

• 値が負の場合： その行は昇順にソートされているため、現在位置より左側の要素（b+1個）はすべて負の数です。まとめてカウントし、次の行へ移動します。

• 値が0以上の場合： 負の数はもっと左側にあるはずなので、列を1つ左へ移動します。

• 計算量： 各ステップで必ず行または列が1つ進むため、時間計算量はO(行数＋列数)。すべての要素を走査する総当たり法のO(行数×列数)と比べて大幅に高速です。

応用：任意の閾値未満の要素数を求める

条件部分のmatrix[a][b] < 0をmatrix[a][b] < nに変更すれば、「n未満の要素の個数」を同じアルゴリズムで求められます。たとえば「5以下の整数の個数」を知りたい場合は、条件を<= 5に置き換えるだけで対応可能です。