264 Ugly Number II
Write a program to find then
-th ugly number.
Ugly numbers are positive numbers whose prime factors only include2, 3, 5
. For example,1, 2, 3, 4, 5, 6, 8, 9, 10, 12
is the sequence of the first10
ugly numbers.
Note that1
is typically treated as an ugly number, andndoes not exceed 1690.
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: L1, L2, and L3.
Assume you have Uk, the kth ugly number. Then Uk+1must be Min(L1* 2, L2* 3, L3* 5).
这题有两个解法,一个是网上抄的,用一个array来存所有的ugly数字。我们用3个不同的index来指出现在2,3和5的ugly数字到哪里了。首先我们把res[0]设为1,第一个udly number是1.然后,我们把3个下标都设成从0开始。每次我们算3个数,然后找最小。每次把生成的这3个数里最小的那个放到第i位ugly number的地方。最后返回res[i - 1]。
另一种做法是cc189里的第17.9.用的是队列,每次也是把最小的乘积找出来,放到适当的队伍里。这里要注意,如果用int的话,在i = 1545的时候会overflow,所以要改用long。
Last updated