Question

Formatted question description: https://leetcode.ca/all/264.html

 264	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.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:
1 is typically treated as an ugly number.
n does not exceed 1690.

@tag-array


Algorithm

Each sublist is an ugly number multiplied by 2, 3, 5,

The required ugly number is taken from the generated sequence,

Every time, the smallest one from the three lists is added to the sequence.

We can maintain three lists of ugly numbers:

1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2, 9*2
1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3, 8*3
1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5, 8*5


Carefully observe the above three lists, you can find that each sublist is an ugly number multiplied by 2, 3, 5, and the required ugly number is taken from the generated sequence, each time from the three lists to take out the smallest one to join the sequence.

Step by step example:

[1]
1,1,1

[1, 2]
2,1,1

[1, 2, 3]
2,2,1

[1, 2, 3, 4]
3,2,1

[1, 2, 3, 4, 5]
3,2,2

[1, 2, 3, 4, 5, 6]
4,3,2

[1, 2, 3, 4, 5, 6, 8]
5,3,2

[1, 2, 3, 4, 5, 6, 8, 9]
5,4,2

[1, 2, 3, 4, 5, 6, 8, 9, 10]
6,4,3


Java