# LeetCode Easy 703. Kth Largest Element in a Stream

tags: leetcode

問題

• Explore
• Problems

アイデア

配列のk番目に大きい要素を常に返すようなクラスを作れという問題です．

必要なのはk番目に大きい値なのでそれより小さい値は使わなくても良いです．

また，配列を常に整列していれば時間計算量を効率化出来ます．

解法

• コンストラクターで大きいものから$K$個をメンバー変数として保持します．
• もし，｢$K$番目までの配列の大きさが$K$以下｣かつ｢$K$番目の要素以下の要素｣のときは何も挿入する必要がないです．
• そうでない場合は，二分探索をして挿入する位置を求めます．
• $K$番目までの配列の大きさが$K$よりも大きくなった場合は最小の要素を取り除きます．

計算量

配列の大きさを$N$とします．

• 時間計算量
  • __init__メソッドでソートするのに$O(N \log N)$
  • addメソッドで$O(N + \log N)$
    • 探索は二分探索をしているので$O(\log N)$
    • 挿入に$O(N)$必要です．
• 空間計算量
  • 大きいものから$K$個の要素の分の配列を用意する必要があるので$O(K)$

Python

class KthLargest(object):
    def __init__(self, k, nums):
        self.top_k = sorted(nums, reverse=True)[:k]
        self.k = k
        
    def add(self, val):
        if len(self.top_k) == self.k and val <= self.top_k[-1]:
            return self.top_k[-1]
        
        left, right = 0, len(self.top_k)
        while left != right:
            
            mid = left + (right - left) // 2
            if val > self.top_k[mid]:
                right = mid
            else:
                left = mid + 1
            
        self.top_k.insert(left, val)
        if len(self.top_k) > self.k:
            self.top_k.pop()
        return self.top_k[-1]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)