各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 77 天。今天力扣上的每日一题是「264. 丑数 II」。

解题思路

今天的题目让我们生成第 n 个丑数。做这样的题目，如果是逐个判断自然数是否为丑数，一定是会超时的。常见的办法是用生成的办法。

要生成第 n 个丑数，我们必须从第一个丑数 1 开始，向后逐渐的寻找。丑数只包含 2， 3，5 三个因子，所以生成方式就是在已经生成的丑数集合中乘以 [2, 3, 5] 而得到新的丑数。

现在的问题是在已经生成的丑数集合中，用哪个数字乘以 2？ 用哪个数字乘以 3？用哪个数字乘以 5？

很显然的一个结论：用还没乘过 2 的最小丑数乘以 2；用还没乘过 3 的最小丑数乘以 3；用还没乘过 5 的最小丑数乘以 5。然后在得到的数字中取最小，就是新的丑数。

  • 我们需要定义 3 个指针 index2, index3, index5 分别表示丑数集合中还没乘过 2，3，5 的丑数位置。
    - 然后每次新的丑数 dp[i] = min(dp[index2] * 2, dp[index3] * 3, dp[index5] * 5) 。
    - 然后根据 dp[i] 是由 index2, index3, index5 中的哪个相乘得到的，对应的把此 index + 1，表示还没乘过该 index 的最小丑数变大了。

代码

  1. class Solution(object):
  2.     def nthUglyNumber(self, n):
  3.         if n < 0:
  4.             return 0
  5.         dp = [1] * n
  6.         index2, index3, index5 = 0, 0, 0
  7.         for i in range(1, n):
  8.             dp[i] = min(2 * dp[index2], 3 * dp[index3], 5 * dp[index5])
  9.             if dp[i] == 2 * dp[index2]: index2 += 1
  10.             if dp[i] == 3 * dp[index3]: index3 += 1
  11.             if dp[i] == 5 * dp[index5]: index5 += 1
  12.         return dp[n - 1]
  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

刷题心得

今天的题目有点绕，主要想一想：该谁乘以 2 了？该谁乘以 3 了？该谁乘以 5 了？

参考资料：
三指针方法的理解方式
GrandYang

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！