题解 | 丑数

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param index int整型 
     * @return int整型
     */
    public int GetUglyNumber_Solution (int index) {
        // write code here
        if(index == 0){
            return 0;
        }
        int[] factors = {2,3,5};
        HashMap<Long, Integer> mp = new HashMap<>();
        // 使用小顶堆记录即将从小到大访问的丑数，保证排序
        PriorityQueue<Long> pq = new PriorityQueue<>();
        mp.put(1L,1);
        pq.offer(1L);
        long res = 0;
        for(int i = 0; i < index; i++){
            // 从小顶堆弹出最小的元素
            res = pq.poll();
            // 每一个丑数都是上一个丑数，*2、*3、*5得来的
            for(int j = 0; j < 3; j++){
                // 乘上因数
                long next = (long) res * factors[j];
                // 去重
                if(!mp.containsKey(next)){
                    mp.put(next,1);
                    pq.offer(next);
                }
            }
        }
        return (int) res;
    }
}