More than 3 years have passed since last update.

LeetCode 1000000本ノック【703. Kth Largest Element in a Stream】

Posted at 2021-05-03

No.	項目
1	概要
2	問題
3	解法
4	ヒープを使った解法（本当はこっちが正答）

概要

●発端
　・競プロ初心者、コーディング面接でズタボロにされ、
　・最低限のアルゴリズム学習とコーディング力強化を習慣化するため記事化
●環境
　・LeetCodeブラウザ上で実装（vscodeに拡張機能にするかもシレナイ）
　・言語はpython3
●その他ルール
　・google検索は自由に（直接的なLeetCodeの問題解説ページはNG）
　　（60分実装して実装出来なければ解説ページ参照）
　・コーディング面接対策のために解きたいLeetCode 60問から問題選出
　・「1000000」は任意の2進数とする

問題

703. Kth Largest Element in a Stream

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
int add(int val) Returns the element representing the kth largest element in the stream.

⇨「リストの中でk番目に大きい値を見つける KthLargest クラスを作成します。
　メソッドは、引数kとnumsを初期化する init と、
　k番目の要素を返す add　の２つです」と書いてあります。知らんけど。

ex1 Input ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output [null, 4, 5, 5, 8, 8]

※仕様がちょっとややこしいかもなので、例題で超絶簡単に整理

["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

↑最初にクラス名(KthLargest)の指定でinitが実行され、下記のように初期化
　k = 3　が　nums = [4, 5, 8, 2]
　初期化処理に戻り値は無いためOutputはnull

["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

↑次はaddのため配列numsに3が追加されてnums は [ 3, 4, 5, 8, 2]となり
　「ソート後にk番目の値を返す」ためOutputは4　※[ 2, 3, 4, 5, 8,]

後は繰り返し繰り返し。。。

解法

実施時間：35分

~~英語読めないと~~少々分かりにくいですが仕様を満たす実装自体は
特に難しくはなかったです。

要件としては

・initメソッド
　k　と nums　を初期化
・addメソッド
　引数valを配列numsに追加し、
　降順ソートの後、
　k番目に大きい値を返す

とシンプルですね。

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.nums = nums

    def add(self, val: int) -> int:
        self.nums.append(val)
        if len(self.nums) >= self.k:
            self.nums.sort()
            return self.nums[-self.k]