import java.util.HashSet;

import java.util.PriorityQueue;

public class NthUglyNumber_49 {

/**

* 采用最小根堆的方式来求解第n个丑数

* @param n

* @return

*/

// 1. 注意这里堆和哈希集中的数据要定义层Long型，否则result*2、result*3、result*5太大会超范围

public int nthUglyNumber(int n) {

int result = 0;

// 定义质因子

int[] factors = {2, 3, 5};

// 定义一个小根堆

PriorityQueue<Long> minHeap = new PriorityQueue<>();

// 定义一个哈希集用来去重

HashSet<Long> set = new HashSet<>();

// 添加第一个元素1

set.add(1L);

minHeap.offer(1L);

for (int i = 0; i < n; i++) {

// 每次循环将栈顶元素出队

long cur = minHeap.poll();

result = (int) cur;

// 将result*2、result*3、result*5入堆

for (int f : factors) {

// 注意这里不能用f*result，要进行long运算否则会超int范围导致数据混乱

long next = f * cur;

// 使用哈希集去重判断

if (set.add(next)) {

minHeap.offer(next);

}

}

}

return result;

}

}