题解 | #丑数 小根堆的应用#

import java.util.*;

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 6){
            return index;
        }
        //set用来判重
        HashSet<Long> set = new HashSet<Long>();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        //小根堆是本作法的核心
        set.add((long) 1);
        heap.offer((long) 1);
        //丑数必定为丑数与2，3，5之积
        int[] nums = new int[]{2,3,5};
        //注意边界条件
        for(int i = 1; i <= index; i++){
            //根据小根堆特性，poll出来的是堆中的最小值###
            long temp = heap.poll();
            if(i == index){
                return (int) temp;
            }
            //将不重复的数加入小根堆中
            for(int j = 0; j < 3; j++){
                if(!set.contains(temp * nums[j])){
                    set.add(temp * nums[j]);
                    heap.offer(temp * nums[j]);
                }
            }
        }
        return -1;
    }
}