ugly-number-ii.md

264. Ugly Number II - 丑数 II

Tags - 题目标签

Description - 题目描述

EN:

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

 

Example 1:

Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

 

Constraints:

• 1 <= n <= 1690

ZH-CN:

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

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language	Runtime	Memory	Submission Time
typescript	76 ms	45.8 MB	2022/04/12 0:13

function nthUglyNumber(n: number): number {
  const dp: number[] = [0, 1];

  if (n === 1) {
    return dp[n];
  }

  let p2 = 1, p3 = 1, p5 = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = Math.min(2 * dp[p2], 3 * dp[p3], 5 * dp[p5]);

    if (dp[i] === 2 * dp[p2]) {
      ++p2;
    }
    if (dp[i] === 3 * dp[p3]) {
      ++p3;
    }
    if (dp[i] === 5 * dp[p5]) {
      ++p5;
    }
  }

  return dp[n];
};

My Notes - 我的笔记

与 剑指 Offer 49. 丑数 相同，可以去参考那边的笔记。