### LeetCode  • ㊗️
• 大家
• offer
• 多多！

## Problem

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

Example 1:

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.


Example 2:

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.


## Code

class Solution {
public int nthUglyNumber(int n) {
int[] res = new int[n];
res = 1;
int i2 = 0;
int i3 = 0;
int i5 = 0;

for(int i = 1; i < n; i++) {
res[i] = Math.min(res[i2] * 2, Math.min(res[i3] * 3, res[i5] * 5));
if(res[i] == res[i2] * 2) i2 += 1;
if(res[i] == res[i3] * 3) i3 += 1;
if(res[i] == res[i5] * 5) i5 += 1;
}

return res[n - 1];
}
}

class Solution:
def nthUglyNumber(self, n: int) -> int:
res =  * n
res = 1
i2 = 0
i3 = 0
i5 = 0

for i in range(1, n):
res[i] = min(res[i2] * 2, min(res[i3] * 3, res[i5] * 5))
if res[i] == res[i2] * 2:
i2 += 1

if res[i] == res[i3] * 3:
i3 += 1

if res[i] == res[i5] * 5:
i5 += 1

return res[-1]