首页 > 代码库 > 264. Ugly Number II
264. Ugly Number II
Write a program to find the n
-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5
. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12
is the sequence of the first 10
ugly numbers.
Note that 1
is typically treated as an ugly number, and n does not exceed 1690.
解题思路:本题重点是要知道一个丑数是另一个丑数*2,*3,*5得到的。
例如已知丑数序列为 1, 2, 3, 4, 5, 6, 8, 9, 10, 12,下一个丑数为第一个大于12的且因子只有2,3,5的数,即min(8*2,6*3,4*5)=16,那么下一个丑数就是min(9*2,6*3,4*5),由此可以看到每次求下一个丑数的时候,之前没有用到的位置的大于当前丑数的值还是要用到的,所以可以用三个指针保存有希望产生当前丑数的值。
class Solution { public: int nthUglyNumber(int n) { vector<int>uglyNum(n,0); int _2=0,_3=0,_5=0; uglyNum[0]=1; for(int i=1;i<n;i++){ uglyNum[i]=min(2*uglyNum[_2],min(3*uglyNum[_3],5*uglyNum[_5])); if(uglyNum[i]==2*uglyNum[_2])_2++; if(uglyNum[i]==3*uglyNum[_3])_3++; if(uglyNum[i]==5*uglyNum[_5])_5++; } return uglyNum[n-1]; } };
264. Ugly Number II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。