Problem

Ugly number is a number that only have factors 3, 5 and 7.

Design an algorithm to find the Kth ugly number. The first 5 ugly numbers are 3, 5, 7, 9, 15 ...

Example

If K=4, return 9.

Note

数组primes是三个基数；初始化以Long.valueOf(x)分别存入。

要存储基数之后按顺序生成的ugly number，可以使用PriorityQueue。

建立PriorityQueue<Long> Q，先放入primes的基数。

建立HashMap，标记Q中已存入的值，必须和放入Q的操作同步。

为了计算后面的ugly number，循环从Q中poll出前端的元素（i=0; i<k; i++）存入新的数num，再循环计算出num和primes中三个数的和。若求得的和num*prime[j]在map中没有标记过，则加入Q里，并在map标记；若标记过，不操作，继续外层poll的循环。当外层循环停止的时候，正好poll出第k个数存入num，return。

用example举例：

//primes = [3, 5, 7];    //Q = {3, 5, 7};        //map = {(3, true), (5, true), (7, true)};    //num = 3: Q.add(9, 15, 21); map.put(9,, 15,, 21, true);    //num = 5: Q.add(15->no, 25, 35), map.put(25,, 35, true);    //num = 7: Q.add(25->no, 35->no, 49), map.put(49, true);    //k = 4: loop i stops, num = 9; ...; return num = 9;

Solution

class Solution {    public long kthPrimeNumber(int k) {        Queue
    
      Q = new PriorityQueue
     
      ();        HashMap
      
        map = new HashMap
       
        ();        Long[] primes = new Long[3];        primes[0] = Long.valueOf(3);        primes[1] = Long.valueOf(5);        primes[2] = Long.valueOf(7);        for (int i = 0; i < 3; i++) {            Q.add(primes[i]);            map.put(primes[i], true);        }        Long num = Long.valueOf(0);        for (int i = 0; i < k; i++) {            num = Q.poll();            for (int j = 0; j < 3; j++) {                if (!map.containsKey(primes[j] * num)) {                    Q.add(primes[j] * num);                    map.put(primes[j] * num, true);                }            }        }        return num;    }}