丑数（Python and C++解法）

题目：

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:

1 是丑数。
n 不超过1690。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chou-shu-lcof

思路：

　　常规思路是从小到大依次判断每个数是不是丑数，这种方法对大量的非丑数进行了计算，效率较低。

本题解法：

如果某个数是丑数，那么它一定是前面一个较小的丑数*2或*3或*5得到的。

　　假设当前已有丑数的最大值是C：

　　　　将C前面的所有丑数*2，会得到一系列新的丑数，选择出第一个大于C的丑数C1；

　　　　将C前面的所有丑数*3，会得到一系列新的丑数，选择出第一个大于C的丑数C2；

　　　　将C前面的所有丑数*5，会得到一系列新的丑数，选择出第一个大于C的丑数C3；

　那么C后面的一个丑数C_next一定是min{C1,C2,C3}。

　在计算一系列新的丑数的时候，进行了一些不必要的计算，如将C前面的所有丑数*2这一计算：C前面一定存在某个丑数C_pre，C_pre前面的丑数*2都小于等于C，而C_pre后面的丑数*2都大于C，只需要记下这个C_pre，然后C_pre*2 = C1,。

使用动态规划完成解答。

Python解法：

 1 class Solution:
 2     def nthUglyNumber(self, n: int) -> int:
 3         dp = [1] * n  # 1是最小的丑数
 4         pre_2, pre_3, pre_5 = 0, 0, 0  # 初始化解题思路中*2、*3、*5计算时的C_pre的下标
 5         for i in range(1, n):
 6             dpby2 = dp[pre_2] * 2
 7             dpby3 = dp[pre_3] * 3
 8             dpby5 = dp[pre_5] * 5
 9             dp[i] = min(dpby2, dpby3, dpby5)
10             if dp[i] == dpby2:  # 更新下标
11                 pre_2 += 1
12             if dp[i] == dpby3:
13                 pre_3 += 1
14             if dp[i] == dpby5:
15                 pre_5 += 1
16         return dp[n-1]

C++解法：

 1 class Solution {
 2 public:
 3     int nthUglyNumber(int n) {
 4         vector<int> dp(n, 1);  // dp数组初始化为n个1
 5         int pre_2 = 0, pre_3 = 0, pre_5 = 0;
 6         for(int i = 1; i < n; i++) {
 7             int dpby2 = dp[pre_2] * 2;
 8             int dpby3 = dp[pre_3] * 3;
 9             int dpby5 = dp[pre_5] * 5;
10             int tempMin  = min(dpby2, dpby3);  // C++ min一次只能比较两个元素
11             dp[i] = min(tempMin, dpby5);
12             if(dp[i] == dpby2)
13                 pre_2 += 1;
14             if(dp[i] == dpby3)
15                 pre_3 += 1;
16             if(dp[i] == dpby5)
17                 pre_5 += 1;
18         }
19         return dp[n-1];
20     }
21 };