# 264. Ugly Number II 丑数 II

https://leetcode.com/problems/ugly-number-ii/open in new window

Total Accepted: 12227 Total Submissions: 54870 Difficulty: Medium

## # Question

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

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

## # Examples

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.

## # Ways

### # 方法二

(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, …

public static int nthUglyNumber2(int n) {
List<Integer> num2List = new ArrayList<Integer>();
List<Integer> num3List = new ArrayList<Integer>();
List<Integer> num5List = new ArrayList<Integer>();

int test = 0;

for (int j = 0; j < n; j++) {
//最小元素
test = Math.min(Math.min(num2List.get(0), num3List.get(0)), num5List.get(0));

//让列表中一直只有一个元素
if (num2List.get(0) == test) num2List.remove(0);
if (num3List.get(0) == test) num3List.remove(0);
if (num5List.get(0) == test) num5List.remove(0);

}

return test;
}

class Solution(object):
def nthUglyNumber(self, n):
if n < 0:
return 0
dp = [1] * n
index2, index3, index5 = 0, 0, 0
for i in range(1, n):
dp[i] = min(2 * dp[index2], 3 * dp[index3], 5 * dp[index5])
if dp[i] == 2 * dp[index2]: index2 += 1
if dp[i] == 3 * dp[index3]: index3 += 1
if dp[i] == 5 * dp[index5]: index5 += 1
return dp[n - 1]

## # Reference

http://blog.csdn.net/guang09080908/article/details/47780619open in new window

http://blog.csdn.net/xudli/article/details/47903959open in new window

## # Date

2015/10/18 20:57:01

2018 年 8 月 28 日 ———— 雾霾天