[LeetCode]Ugly Number II | 书影博客

[LeetCode]Ugly Number II | 书影博客

题目描述：

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Hint:

The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.

An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.

The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L₁, L₂, and L₃.

Assume you have U_k, the kth ugly number. Then U_k+1 must be Min(L₁ * 2, L₂ * 3, L₃ * 5).

题目大意：

编写程序寻找第n个"丑陋数" ugly number

丑陋数是指只包含质因子2, 3, 5的正整数。例如，1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前10个丑陋数。

注意，数字1也被视为丑陋数

提示：

朴素的方法是对每一个数字重复调用isUgly方法，直到找到第n个为止。但是大部分数字都不是丑陋的。尝试寻找只生成丑陋数的方法

丑陋数必须由一个较小的丑陋数乘以2,3或者5得到

解决问题的关键是维护丑陋数的顺序。尝试一个类似于合并3个有序列表L₁,L₂与L₃的方法

假设你当前计算出了第k个丑陋数U_k。则U_k+1一定是Min(L₁ * 2, L₂ * 3, L₃ * 5)

解题思路：

参考：http://www.geeksforgeeks.org/ugly-numbers/

丑陋数序列可以拆分为下面3个子列表：

(1) 1×2, 2×2, 3×2, 4×2, 5×2, … (2) 1×3, 2×3, 3×3, 4×3, 5×3, … (3) 1×5, 2×5, 3×5, 4×5, 5×5, …

我们可以发现每一个子列表都是丑陋数本身(1, 2, 3, 4, 5, …) 乘以 2, 3, 5

接下来我们使用与归并排序相似的合并方法，从3个子列表中获取丑陋数。每一步我们从中选出最小的一个，然后向后移动一步。

Read full article from [LeetCode]Ugly Number II | 书影博客