剑指offer---ugly number

本文主要是介绍剑指offer---ugly number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解题思路：使用heap的方式进行排序处理，然后分别从其中向外取出数据。

java

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;public class Solution {public int GetUglyNumber_Solution(int index) {if (index <= 0) {return 0;}if (index == 1) {return 1;}Set<Long> set = new HashSet<>();Queue<Long> pq = new PriorityQueue<>();set.add((long)1);pq.offer((long)1);int count = 0;long val = 0;int[] arr = new int[] {2, 3, 5};while (count < index) {val = pq.poll();set.remove(val);count++;for (int i = 0; i < 3; i++) {if (set.contains(val * arr[i])) {continue;} else {pq.offer(val * arr[i]);set.add(val * arr[i]);}}}return (int)val;}
}

这篇关于剑指offer---ugly number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---