给你一个整数 n ,请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1:
输入:n = 10 输出:12 解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2:
输入:n = 1 输出:1 解释:1 通常被视为丑数。
提示:
1 <= n <= 1690
动态规划法。
定义数组 dp,dp[i - 1] 表示第 i 个丑数,那么第 n 个丑数就是 dp[n - 1]。最小的丑数是 1,所以 dp[0] = 1。
定义 3 个指针 p2,p3,p5,表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时,三个指针的值都指向 0。
当 i∈[1,n),dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5),然后分别比较 dp[i] 与 dp[p2] * 2、dp[p3] * 3、dp[p5] * 5 是否相等,若是,则对应的指针加 1。
最后返回 dp[n - 1] 即可。
class Solution: def nthUglyNumber(self, n: int) -> int: dp = [1] * n p2 = p3 = p5 = 0 for i in range(1, n): next2, next3, next5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5 dp[i] = min(next2, next3, next5) if dp[i] == next2: p2 += 1 if dp[i] == next3: p3 += 1 if dp[i] == next5: p5 += 1 return dp[-1]
class Solution { public int nthUglyNumber(int n) { int[] dp = new int[n]; dp[0] = 1; int p2 = 0, p3 = 0, p5 = 0; for (int i = 1; i < n; ++i) { int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5; dp[i] = Math.min(next2, Math.min(next3, next5)); if (dp[i] == next2) ++p2; if (dp[i] == next3) ++p3; if (dp[i] == next5) ++p5; } return dp[n - 1]; } }
class Solution { public: int nthUglyNumber(int n) { vector<int> dp(n); dp[0] = 1; int p2 = 0, p3 = 0, p5 = 0; for (int i = 1; i < n; ++i) { int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5; dp[i] = min(next2, min(next3, next5)); if (dp[i] == next2) ++p2; if (dp[i] == next3) ++p3; if (dp[i] == next5) ++p5; } return dp[n - 1]; } };
/** * @param {number} n * @return {number} */ var nthUglyNumber = function (n) { let dp = [1]; let p2 = 0, p3 = 0, p5 = 0; for (let i = 1; i < n; ++i) { const next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5; dp[i] = Math.min(next2, Math.min(next3, next5)); if (dp[i] == next2) ++p2; if (dp[i] == next3) ++p3; if (dp[i] == next5) ++p5; dp.push(dp[i]); } return dp[n - 1]; };
func nthUglyNumber(n int) int { dp := make([]int, n) dp[0] = 1 p2, p3, p5 := 0, 0, 0 for i := 1; i < n; i++ { next2, next3, next5 := dp[p2]*2, dp[p3]*3, dp[p5]*5 dp[i] = min(next2, min(next3, next5)) if dp[i] == next2 { p2++ } if dp[i] == next3 { p3++ } if dp[i] == next5 { p5++ } } return dp[n-1] } func min(a, b int) int { if a < b { return a } return b }
public class Solution { public int NthUglyNumber(int n) { int[] dp = new int[n]; dp[0] = 1; int p2 = 0, p3 = 0, p5 = 0; for (int i = 1; i < n; ++i) { int next2 = dp[p2] * 2, next3 = dp[p3] * 3, next5 = dp[p5] * 5; dp[i] = Math.Min(next2, Math.Min(next3, next5)); if (dp[i] == next2) { ++p2; } if (dp[i] == next3) { ++p3; } if (dp[i] == next5) { ++p5; } } return dp[n - 1]; } }