#yyds幹貨盤點# 解決劍指offer：醜數

1.簡述：

描述

把隻包含質因子2、3和5的數稱作醜數（Ugly Number）。例如6、8都是醜數，但14不是，因為它包含質因子7。 習慣上我們把1當做是第一個醜數。求按從小到大的順序的第 n個醜數。

資料範圍：

要求：空間複雜度  ， 時間複雜度 

示例1

輸入：

7      

8      

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        //排除0
        if(index == 0)
            return 0; 
        //要乘的因數
        int[] factors = {2, 3, 5}; 
        //去重
        HashMap<Long, Integer> mp = new HashMap<>();
        //小頂堆
        PriorityQueue<Long> pq = new PriorityQueue<>(); 
        //1先進去
        mp.put(1L, 1);
        pq.offer(1L);
        long res = 0;
        for(int i = 0; i < index; i++){ 
            //每次取最小的
            res = pq.poll(); 
            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;
    }
}