Ugly Number II

这是我第一次参加 LeetCode (力扣) 的每月挑战题组，希望留下点笔记，大家可以参考和互相讨论。😃

第四天问：

请写一个可以找第 n^th 丑陋数 (ugly number) 的程序。

定义：丑陋数的因数只包括1, 2, 3, 5和比它小的丑陋数，且该四个数字也是丑陋数。

题目例子 (引用自LeetCode)：

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.

提示：

最暴力的方法就是弄一个 isUgly 方法一个一个数字遍历去找，直到找到第 n^th 个丑陋数。但是，大部分数字都不是丑陋数 (ps: 尤其是当 n 很大又要遍历去找时)，所以请集中资源去产出对应的丑陋数。丑陋数一定是由 2, 3, 5 或者较小的丑陋数。关键是如何管理所计算出的丑陋数的排列，可以嘗试一个类似合并三个已排序列表 L₁, L₂ 和 L₃ 的方法。假设你现在有第 k^th 个丑陋数 U_k, 那么第 (k+1)^th 个丑陋数 U_k+1 ，就一定是 Min(L₁ * 2, L₂ * 3, L₃ * 5).

解题思路：

这道题难在怎么可以快速找到结果所需要的那一個 n^th ugly number。第一个想法是直接逐个算，但是如果 n 稍为大一点 (例如 300)，所需时间都太长了，不符合题目要求。

以下这段代因为时间复杂度太高，因为time limit exceeded被打回了…… (这个时间复杂度不太会算，有错请告知🙏)

失败代码 (时间复杂度：O(2ⁿ))

class Solution: seq = [] def nthUglyNumber(self, n: int) -> int: counter = 0 start = 1 while counter < n: if self.isUgly(start): self.seq.append(start) counter += 1 start += 1 print(self.seq) return start - 1 def isUgly(self, num: int): if num == 1 or num == 2 or num == 3 or num == 5: return True elif num in self.seq: return True elif num % 2 == 0: return self.isUgly(num/2) elif num % 3 == 0: return self.isUgly(num/3) elif num % 5 == 0: return self.isUgly(num/5) else: return False

那好，我们就根据提示做一遍。本来不是很容易理解，所以上网看了点资料。原理是这样的 (我们先列出前三十个数做个例子)：

因数 \ 丑陋数1234568910122 (L₁)2x12x22x32x42x52x62x82x92x102x123 (L₂)3x13x23x33x43x53x63x83x93x103x125 (L₃)5x15x25x35x45x55x65x85x95x105x12

提示 3 和 4 总结起来就是说：每个丑陋数的下一个数，肯定是 L₁, L₂ 和 L₃ 之间还未排序的最小数。简单来说，就是假设你有这三个列表，把它们排序成一个列表：而已知每个丑陋数也是从前面比较小的数得出，所以有了以下代码：

代码 (时间复杂度： O(log n))

class Solution: def nthUglyNumber(self, n: int) -> int: if n <= 0: return 0 index2 = 0 # L1列表的起始指针, 对应上面表格第一栏 index3 = 0 # L2列表的起始指针 index5 = 0 # L3列表的起始指针 seq = [1] * n # 已知需要n个丑陋数 for i in range(1, n): seq[i] = min(seq[index2]*2, seq[index3]*3, seq[index5]*5) # 找三个中最小，放到总列做排序 # 移动对应列表的指针，找下一个未排序的数 if seq[i] == 2 * seq[index2]: index2 += 1 if seq[i] == 3 * seq[index3]: index3 += 1 if seq[i] == 5 * seq[index5]: index5 += 1 return seq[n - 1]

Reference/参考资料:

https://blog.csdn.net/fuxuemingzhu/article/details/49231615 https://www.cnblogs.com/grandyang/p/4743837.html http://fisherlei.blogspot.com/2015/10/leetcode-ugly-number-ii-solution.html