剑指offer-丑数
剑指offer-丑数
描述
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
求解思路:
思路1:
首先编写函数,判断某一个数是否属于丑数。
然后通过循环找到第index个丑数。
1 int GetUglyNumber_Solutions(int index) { 2 int count=0; 3 int num=1; 4 while(count<index){ 5 if(isUglyNum(num)){ 6 count++; 7 } 8 ++num; 9 }10 return --num;11 }12 13 // 没仔细看题目,以为是要判断一个数是否是丑数14 // 事实证明,挨个判别会导致运行超时。15 bool isUglyNum(int num){16 // 过滤的思想,依次把2,3,5因子全都刷掉,看结果是不是117 while(num%2==0) num=num/2;18 while(num%3==0) num=num/3;19 while(num%5==0) num=num/5;20 if(num==1) return true;21 return false;22 }
果然,很顺利地超时了。
思路2:
假设我们现有已经有了一个丑数的数组exit,那我们的任务就是确定这个数组的下一个丑数。
由于丑数必定可分解为2*x、3*y以及5*z三者的至少其中之一,现在的任务变成了:
记录x,y,z的值,使得2x,3y,5z的值刚好稍大于现有数组的最后一个元素。
取2x,3y,5z三者的最小值,即为下一个丑数。
1 class Solution { 2 public: 3 int GetUglyNumber_Solution(int index) { 4 // 题目提示二分,那就老老实实用二分吧 5 // 没思路,怎么用到二分的? 6 // 题解的思路:由于丑数是由已有的丑数队列乘2,3,5得到的 7 // 所以确定现有的丑数队列后,怎么确定下一个最小的丑数呢? 8 // 这个数可能会被分解乘2*x,3乘y,5乘z,这三个值取最小值就是下一个丑数了 9 // 那么x,y,z怎么求呢?用指针10 vector<int> exit={1};11 int p2=0,p3=0,p5=0; // 三个指针首先都指向112 for(int i=0;i<index;++i){13 int newUgly=min(2*exit[p2],min(3*exit[p3],5*exit[p5]));14 exit.push_back(newUgly);15 if(newUgly==2*exit[p2]) ++p2; // 不移动的话永远是这个最小16 if(newUgly==3*exit[p3]) ++p3;17 if(newUgly==5*exit[p5]) ++p5;18 }19 return exit[index-1];20 }21 };
心之所愿,永不相忘
分类: C++