题目描述

把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含质因子 7。 习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 n 个丑数

提示：

• 1 是丑数。
• n 不超过1690。

测试用例

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

思路

首先从丑数的定义我们知道，一个丑数的因子只有 2,3,5，那么丑数 p = 2 ^ x * 3 ^ y * 5 ^ z

换句话说一个丑数一定由另一个丑数乘以 2 或者乘以 3 或者乘以 5 得到

那么我们从 1 开始乘以 2,3,5，就得到 2,3,5 三个丑数，在从这三个丑数出发乘以 2,3,5 就得到 4,6,10, 6,9,15, 10,15,25 九个丑数

因为这 9 个数可能会有重复的，所以从这 9 个丑数中拿出最小的数（要比丑数数组中的数大）加入丑数数组

(1) 丑数数组 [1]

• 乘以 2：2
• 乘以 3：3
• 乘以 5：5

把 2 放入丑数数组

(2) 丑数数组 [1,2]

• 乘以 2：2 4
• 乘以 3：3 6
• 乘以 5：5 10

把 3 放入丑数数组

代码实现

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入n: ");
let n = Number(readline());

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function (n) {
  if (n === 0) {
    return 0;
  }
  // 存储丑数的数组 —— 保证从小到大排序
  let res = [1];
  while (res.length < n) {
    // 遍历数组中的元素
    // 乘2 —— 得到比此时丑数数组最后一个元素大的值
    let n2 = res
      .map((item) => item * 2)
      .find((item) => item > res[res.length - 1]);

    // 乘3 —— 得到比此时丑数数组最后一个元素大的值
    let n3 = res
      .map((item) => item * 3)
      .find((item) => item > res[res.length - 1]);
    // 乘5 —— 得到比此时丑数数组最后一个元素大的值
    let n5 = res
      .map((item) => item * 5)
      .find((item) => item > res[res.length - 1]);
    // 取三个操作得到的最小值，放入丑数数组
    res.push(Math.min(n2, n3, n5));
  }

  return res[n - 1];
};

const res = nthUglyNumber(n);
console.log("结果为: ", res);

/* 
  请输入n:
  10
  结果为:  12
*/