もっと辛い(java)

5188 ワード
Lv2 Java プログラマ PriorityQueue テキストリンク

問題の説明



考える

  • scovilleの長さは最大10,000,000であるため,最小値を直接検索するPriorityQueue最小hipを用いる.
    • 最小値がkより小さい場合は
  • を繰り返し、要素が1つ残っている場合は-1を返します.

    説明する

    import java.util.PriorityQueue;
class Solution {
    public int solution(int[] scoville, int K) {
        int ans = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        
        for( int i : scoville) heap.offer(i);
        
        while(heap.peek() < K){
            if(heap.size() == 1) return -1;
            
            int a = heap.poll();
            int b = heap.poll();
            int sum = a + ( b * 2 );
            heap.offer(sum);
            ans++;
        }
        return ans;
    }
}
    これは、データ量が多く、その中から最小値を2つ抽出して追加する必要があるという問題であるため、優先順位キューを考慮する必要がある.
    Javaでは、PriorityQueueは、時間複雑度N(1)から最大N(LogN)までのバイナリツリーを使用します.
    PriorityQueueの機能を見てみましょう
    .peek()->最も優先度の高い要素を取得します.(追加された値は優先順位で並べ替えられます)
    要素を.prove()->queueに入れます.
    .poll()->優先度が最も高い要素を返します.
    .remove()->最も優先度の高い要素を削除します.
    .size()->queueのサイズを返します.
    これらの技能を利用して問題を解くなら、難しくない.
    • Junitユニットテスト実行の手順
    Phaser Tutorial Webパッケージ(3)