Description
Ugly number is a number that only have prime factors 2, 3 and 5.
Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
Note that 1 is typically treated as an ugly number.
Example
Example 1:
Input: 9
Output: 10
Example 2:
Input: 1
Output: 1
Challenge
O(n log n) or O(n) time.
思路：
因为时间复杂度的要求，用挨个遍历判断是不是丑数的方法会不满足要求，效率太低，又根据丑数的性质，后面一个丑数肯定是前面某个丑数的2，3，5倍，又因为取出来的丑数要排好序，就想到了利用heap的性质，将前面每个丑数的倍数放进heap里。时间复杂度为O(nlogn).
另外如果要判断一个数是不是丑数的代码是，用那个数逐个除以2, 3, 5直到不能整除，然后将商作为除以下一个数的基础，除到最后看下是否是1，是1就是丑数。
代码：
网友评论