剑指offer49 丑数【双指针】
题目描述
我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。
示例:
1 | 输入: n = 10 |
说明:
1
是丑数。n
不超过1690。
解题思路
利用三个指针的方法,分别指向2,3,5的系数的位置,系数都为1开始,如果当前的数为系数于2,3,5的乘积,则系数右移一个数。
实现代码
1 | class Solution { |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)
资料
剑指offer49 丑数【双指针】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.