阅读 160

剑指offer-丑数

剑指offer-丑数

描述

把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

求解思路:

思路1:

  1. 首先编写函数,判断某一个数是否属于丑数。

  2. 然后通过循环找到第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:

  1. 假设我们现有已经有了一个丑数的数组exit,那我们的任务就是确定这个数组的下一个丑数。

  2. 由于丑数必定可分解为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++


文章分类
后端
文章标签
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐