Pythonでストリーム内のK番目に大きい要素を求める方法

本記事では、データストリームの中からK番目に大きい要素を求めるクラスをPythonで設計する方法を解説します。ここでの「K番目に大きい」とは、ソート順におけるK番目の位置にある要素を指し、重複を除いた「K番目に大きい値（distinct）」とは異なる点に注意してください。

問題の概要

KthLargest クラスは、整数 k と初期データを格納した配列 nums を受け取るコンストラクタを持ちます。その後、add(val) メソッドが呼び出されるたびに、新しい値をストリームに追加し、その時点でのK番目に大きい要素を返します。

動作例

例えば、k = 3、初期要素が [4, 5, 8, 2] の場合を考えてみましょう。続けて add(3)、add(5)、add(10)、add(9)、add(4) を呼び出すと、それぞれの出力は 4, 5, 5, 8, 8 となります。

アルゴリズムの手順

この問題は以下の手順で解決できます。

• イニシャライザ（__init__）を定義する。引数として k と nums を受け取る。
  • array := nums として初期配列を保持する。
• add() 関数を定義する。引数として val を受け取る。
  • val を配列の末尾に挿入する。
  • 配列全体をソートする。
  • array[配列の長さ - k] を返す。

実装コード

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

class KthLargest:
    def __init__(self, k, nums):
        self.array = nums
        self.k = k

    def add(self, val):
        self.array.append(val)
        self.array.sort()
        return self.array[len(self.array) - self.k]


ob = KthLargest(3, [4, 5, 8, 2])
print(ob.add(3))
print(ob.add(5))
print(ob.add(10))
print(ob.add(9))
print(ob.add(4))

入力

ob.add(3)
ob.add(5)
ob.add(10)
ob.add(9)
ob.add(4)

出力

4
5
5
8
8

処理の流れと計算量について

このシンプルな実装では、add() メソッドが呼ばれるたびに配列を再ソートしています。ソートの計算量は O(n log n) であるため、データ量が多い場合や add() の呼び出しが頻繁な場合は非効率になる可能性があります。

より効率的なアプローチとしては、ヒープ（優先度付きキュー）を使用する方法があります。サイズ k の最小ヒープを維持することで、各 add() 操作を O(log k) で処理でき、常にヒープの先頭がK番目に大きい要素となります。Pythonでは標準ライブラリの heapq モジュールを使うことで簡単に実装できます。

ただし、学習目的や小規模なデータセットであれば、上記のソートベースの実装でも十分に動作し、ロジックも直感的で理解しやすいというメリットがあります。