算法 - 剑指Offer 丑数

题目

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

解题思路

这题我使用最简单方法去做， 首先我们可以获取所有2n,3n,5*n的丑数，只是我们这里暂时无法排序，并且可能存在重复数字的问题， 重复数字用set集合去去重就可以了， 排序问题使用了最小堆去处理这个问题， 最小堆弹出的值一定是所有值中最小的数字， 然后我们弹出n次,第n次弹出的值就是我们需要的值也就是结果，下面就是代码实现。

Java代码实现

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
public class NthUglyNumber {public int nthUglyNumber(int n) {//最小堆//这里使用long是为了解决Int超过最大值的问题Queue<Long> queue = new PriorityQueue();Set<Long> set = new HashSet();int[] nums = {2,3,5};int res = 1;queue.add(1L);set.add(1L);for (int i = 0; i < n; i++) {long head = queue.poll();res = (int)head;for (int nu: nums) {long tmp = nu * head ;if(!set.contains(tmp)){set.add(tmp);queue.add(tmp);}}}return  res;}
}