首页 > 代码库 > 剑指OFFER之丑数(九度OJ1214)
剑指OFFER之丑数(九度OJ1214)
题目描述:
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
- 输入:
输入包括一个整数N(1<=N<=1500)。
- 输出:
可能有多组测试数据,对于每组数据,
输出第N个丑数。
- 样例输入:
3
- 样例输出:
3
解题思路:
最简单的思路是,从1到大数,每个数都检测一遍是否是丑数,检测方法可以考虑
int ugly(int number){ if(number%2 == 0){ return ugly(number/2); }else if(number%3 == 0){ return ugly(number/3); }else if(number%5 == 0){ return ugly(number/5); }else return number==1?true:false;}
可是这种思路,会浪费大量的时间,最后就会超时。
我们考虑一个数组,数组存储的是当前的丑数,以后的每个丑数,都是用之前的数组的元素相乘的来的。接下来就是如何得到后面的丑数并保证它是有序的。
可以想到,数组的第一个元素是1,1与2 3 5分别相乘,可以得到三个值,这三个值里面最小的,肯定就是下一个丑数的最大值,接着max2的下标后移,继续比较。
void mkUglyNumber(){ gArr[top++] = 1; int *max2 = gArr; int *max3 = gArr; int *max5 = gArr; while(top < 1500){ int min = getMin(*max2*2,*max3*3,*max5*5); gArr[top] = min; while(*max2*2 <= gArr[top]) ++max2; while(*max3*3 <= gArr[top]) ++max3; while(*max5*5 <= gArr[top]) ++max5; ++top; }}
比如,当前的数组元素只是1,那么与2 3 5 相乘得到2 3 5,显然得到的最小值是2。数组元素变为1 2。
下标这回变为2 1 1,继续与2 3 5相乘,得到4 3 5,找出其中最小的,再放进数组,元素变为1 2 3。
继续,直到找到1500个丑数之后,每次进行读取丑数即可。
全部代码:
#include <stdio.h>#define MAXSIZE 1500void mkUglyNumber();int getMin(int max2,int max3,int max5);int gArr[MAXSIZE];int top;int main(){ int n; top = 0; mkUglyNumber(); while(scanf("%d",&n)!=EOF && n>=1 && n<=1500){ printf("%d\n",gArr[n-1]); } return 0;}void mkUglyNumber(){ gArr[top++] = 1; int *max2 = gArr; int *max3 = gArr; int *max5 = gArr; while(top < 1500){ int min = getMin(*max2*2,*max3*3,*max5*5); gArr[top] = min; while(*max2*2 <= gArr[top]) ++max2; while(*max3*3 <= gArr[top]) ++max3; while(*max5*5 <= gArr[top]) ++max5; ++top; }}int getMin(int max2,int max3,int max5){ int min = max2<max3?max2:max3; return min<max5?min:max5;}/************************************************************** Problem: 1214 User: xhalo Language: C Result: Accepted Time:10 ms Memory:920 kb****************************************************************/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。