leetcode：264. 丑数 II

题目

给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例：

  1. 输入：n = 10
  2. 输出：12
  3. 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
输入：n = 1
输出：1
解释：1 通常被视为丑数。

本题同：
[中等] 剑指 Offer 49. 丑数

解答 & 代码

丑数 × 2、3、5 还是丑数

动态规划（三指针）：

  • 动态规划数组 dp：dp[i] 表示第 i + 1 个丑数
  • 状态转移方程：dp[i] = min(dp[idx2] × 2, dp[idx3] × 3, dp[idx5] × 5)
    • 指针 idx2、idx3、idx5 分别指向丑数 dp[idx2]、dp[idx3]、dp[idx5]，代表上一个丑数，分别乘上质因数 2、3、5，三者中最小的就是下一个丑数
    • dp[idx2]、dp[idx3]、dp[idx5]三者中最小的数对应的指针 +1（可能有多个值都是最小值，指针都要 + 1，以跳过重复丑数）

  • 初始化：

    • dp[0] = 1，即第 1 个丑数是 1
    • idx2 = 0, idx3 = 0, idx5 = 0
      class Solution {
public:
int nthUglyNumber(int n) {
   // 动态规划数组 dp：dp[i] 表示第 i + 1 个丑数
   vector<int> dp(n);
   // 初始化：第一个丑数为 1
   dp[0] = 1;
   int idx2 = 0, idx3 = 0, idx5 = 0;    // 上一个丑数，都指向第一个丑数的位置
   // 状态转移
   for(int i = 1; i < n; ++i)
   {
       dp[i] = min(dp[idx2] * 2, min(dp[idx3] * 3, dp[idx5] * 5));
       if(dp[i] == dp[idx2] * 2)
           ++idx2;
       if(dp[i] == dp[idx3] * 3)
           ++idx3;
       if(dp[i] == dp[idx5] * 5)
           ++idx5;
   }
   return dp[n - 1];
}
};
      复杂度分析：设求第 n 个丑数

  • 时间复杂度 O(n)：

  • 空间复杂度 O(n)：

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 92.17% 的用户
内存消耗：7.4 MB, 在所有 C++ 提交中击败了 80.97% 的用户