実現したいこと
LeetCodeの703. Kth Largest Element in a Streamを理解したい
前提
この問題はある時点で配列の中でK番目の大きさの値を求めるというものです。
以下は理解しているつもりです。
- min heap
- max heap
- classについて
- コンストラクタについて
ChatGPTや他の解答を見たのですが理解できない箇所があったので教えていただきたいです。
ChatGPTの解答
ts
1class KthLargest {2 private heap: number[];3 private readonly k: number;4 5 constructor(k: number, nums: number[]) {6 this.k = k;7 this.heap = [];8 9 // 初期配列の要素をヒープに追加10 for (let num of nums) {11 this.add(num);12 }13 }14 15 add(val: number): number {16 // 新しい値をヒープに追加17 this.heap.push(val);18 this.heap.sort((a, b) => a - b);19 20 // ヒープのサイズがkより大きい場合は、最小要素を削除21 while (this.heap.length > this.k) {22 this.heap.shift(); // 最小値(配列の先頭)を削除23 }24 25 // k番目に大きい要素を返す(ヒープのルート)26 return this.heap[0];27 }28}29
わからないところ/ 該当のソースコード
ts
1 // ヒープのサイズがkより大きい場合は、最小要素を削除2 while (this.heap.length > this.k) {3 this.heap.shift(); // 最小値(配列の先頭)を削除4 }5 6 // k番目に大きい要素を返す(ヒープのルート)7 return this.heap[0];8 }
上記箇所が理解できません。特に「最小値(配列の先頭)を削除」しているところです
K番目に大きな要素を返すのに消す必要があるのでしょうか?
条件では与えられたK番目の大きさの値を聞かれているだけです。削除する必要がないように感じます。
例)
k=3nums= [1, 2, 3]addが実行されて4が追加された場合、heap=[1, 2, 3, 4]- この時点で
k=3なので3が返される
しかし、他の回答を見てもなぜか先頭を削除してheap=[2,3,4]として4を正解としています
補足情報(FW/ツールのバージョンなど)
https://www.geeksforgeeks.org/kth-largest-element-in-a-stream/

0 コメント