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: L1, L2, and L3.
- Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

**Understand the problem:**

We can maintain three lists of ugly numbers:

1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2, etc..

1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3, etc..

1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5, etc...

Then we can see that in each list, the ugly number is the ugly number itself times 2, 3 or 5.

Then we can maintain three pointers of i, j, and k, and the next ugly number must be minimum number of Li, Lj and Lk. At last, we move forward the pointer.

**Code (Java):**

public class Solution { public int nthUglyNumber(int n) { if (n <= 0) { return 0; } List<Integer> nums = new ArrayList<>(); nums.add(1); int i = 0; int j = 0; int k = 0; while (nums.size() < n) { int m2 = nums.get(i) * 2; int m3 = nums.get(j) * 3; int m5 = nums.get(k) * 5; int mn = Math.min(Math.min(m2, m3), m5); nums.add(mn); if (mn == m2) { i++; } if (mn == m3) { j++; } if (mn == m5) { k++; } } return nums.get(nums.size() - 1); } }

## No comments:

## Post a Comment