264. 丑数 II

原题链接：LeetCode 264. 丑数 II

题目描述

给你一个整数 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`

难度： Medium

题解代码

javascript

/**
 * @param {number} n
 * @return {number}
 */
// const isUgly = num => {
//   while (num % 2 === 0) num /= 2
//   while (num % 3 === 0) num /= 3
//   while (num % 5 === 0) num /= 5
//   return num === 1
// }
// // 可以这样做  但是时间复杂度太高  会超时
// var nthUglyNumber = function(n) {
//   let count = 0
//   let idx = 0
//   while (count < n) {
//     if (isUgly(idx)) count++
//   }
//   return idx
// };


var nthUglyNumber = function(n) {
  // 3个指针 当前丑数*2 *3 *5就会大于丑数数组最大的值
  let p1 = p2 = p3 = 1
  let dp = [0, 1]
  for (i = 2; i <= n; i++) {
    const M1 = dp[p1]*2, M2 = dp[p2]*3, M3 = dp[p3]*5
    dp[i] = Math.min(M1, M2, M3)
    if (dp[i] === M1) p1++
    if (dp[i] === M2) p2++
    if (dp[i] === M3) p3++
  }
  return dp[n]
};

264. 丑数 II #

题目描述 #

题解代码 #

264. 丑数 II

题目描述

题解代码