丑数:求第n个丑数
我们把只包含因子2、3和5的数称作丑数(Ugly Number)。例如,6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当作第一个丑数。
求按从小到大顺序的第1500个丑数?
方法一:
根据丑数的定义,我们想到如果一个数能被2整除,就连续除于2;如果能被3整除,就连续除于3;如果能被5整除,就连续除于5。如果最后得到的是1,那么这个数就是丑数;否则不是。
所以我们可以写出下面的代码:
#include<stdio.h>
int IsUgly( int number )//判断一个整数是不是丑数
{
while( number % 2 == 0 )
number /= 2;
while( number % 3 == 0 )
number /= 3;
while( number % 5 == 0)
number /= 5;
return (number == 1) ? true : false;
}
int GetUglyNumber( int index )//按顺序判断每个整数是不是丑数
{
if(index <= 0)
return 0;
int number =0;
int uglyFound =0;
while(uglyFound < index)
{
++number;
if(IsUgly(number))
{
++uglyFound;
}
}
return number;//返回第index的丑数值
}
int main()
{
printf("%d\n",GetUglyNumber(1500));
return 0;
}
上面的算法虽然直观简洁,但是每一个整数是不是丑数它都要经过计算,时间效率不高,找到第1500个丑数在我的计算机上跑了42秒。
方法二:
我们可以用另一种空间换时间的解法,根据丑数的定义我们知道丑数应该是另一个丑数乘以2、3或者5的结果(1除外)。我们可以创建一个数组,里面存放排好序的丑数,就不需要花时间计算非丑数了。
假设数组中已经有若干个排好序的丑数,最大丑数为M,接下来分析如何生成下一个丑数。这个丑数一定是前面数组中某一个丑数乘以2、3或者5的结果,所以先考虑把已有的每个丑数乘以2。我们可以得到若干个小于等于M和大于M的结果。因为是排好序的,我们只需要找到第一个大于M的结果记为。同样,把已有的每个丑数乘以3和5,找到第一大于M的结果和。那么下一个丑数就是这3个数的最小者。
上面分析的时候把已有的丑数都乘以2、3和5,其实也不是必须的,因为对于已有的丑数乘以2而言,一定存在丑数,排在它之前的丑数乘以2结果都小于已有的最大丑数,在它之后的丑数乘以2都大于已有的最大丑数,所以我们只需要记下这个丑数的位置,同时通过每次生成的新的丑数去更新。乘以3和5而言,同样存在和。
代码如下:
#include<stdio.h>
int Min(int number1,int number2,int number3)
{
int min = (number1 < number2) ? number1 :number2;
min = (min < number3) ? min:number3;
return min;
}
int GetUglyNumber_2(int index)
{
if(index <= 0)
return 0;
int *pUglyNumbers = new int[index];
pUglyNumbers[0] = 1;
int nextUglyIndex = 1;
int *pMultiply2 = pUglyNumbers;
int *pMultiply3 = pUglyNumbers;
int *pMultiply5 = pUglyNumbers;
while(nextUglyIndex < index)
{
int min = Min(*pMultiply2 * 2,*pMultiply3 * 3,*pMultiply5 * 5);
pUglyNumbers[nextUglyIndex] = min;
while(*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex])
++pMultiply2;
while(*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex])
++pMultiply3;
while(*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex])
++pMultiply5;
++nextUglyIndex;
}
int ugly = pUglyNumbers[nextUglyIndex - 1];
delete[] pUglyNumbers;
return ugly;
}
int main()
{
printf("%d\n",GetUglyNumber_2(1500));
return 0;
}
运行结果:
第二种运行时不到一秒就可以计算出结果,但它创建了能容纳1500个丑数的数组,占据约6KB的内存大小。 总的来说,第二种相当于用较小的空间消耗换取了时间效率的提升。
毕竟时间是最重要的,时代的发展,硬件都会变的越来越便宜,人们越来越看重的也都是时间效率,如速度与激情一样,好的跑车都是比较几秒能够提到多少迈,而好的代码都是比较最快得到运行结果。
上一篇: 二叉树的创建:根据前序中序、中序后序递归创建二叉树
下一篇: 设定关系(A=1,B=2,C=3,···,Z=26,AA=27,AB=28,···,AAA=XXX,···),写一个转换函数,根据上面规则把一个字符串转换为数字。
推荐阅读
-
python 输入一个数n,求n个数求乘或求和的实例
-
剑指offer33:求按从小到大的顺序的第N个丑数。
-
问题描述 输入一个自然数n,求小于等于n的素数之和
-
输入一个自然数n,求小于等于n的素数之和?
-
【卡拉兹猜想】:对于一个自然数n,如果他是偶数,那么把它砍掉一半;如果是奇数,那么把(3n+1)砍掉一半,一直反复下去,最后在某一步得到n=1。求从n计算到1的步数
-
1)的累加和(累乘积(阶乘))。其中n的值从键盘输入。输入一个2000年以后的年份n,输出所有介于2">
PTA判断输入的整数是否是素数,如果是则输出"1",否则输出"0." 编写程序,求自然数1至n(n>1)的累加和(累乘积(阶乘))。其中n的值从键盘输入。输入一个2000年以后的年份n,输出所有介于2
-
python 输入一个数n,求n个数求乘或求和的实例
-
【数位dp】求不超过n的数中,有多少个包含2018
-
剑指offer33:求按从小到大的顺序的第N个丑数。
-
php中两个**可以直接求一个数的n次方 为什么还要有pow()函数