剑指 offer代码解析——面试题34丑数

本题详细解析均在代码注释中:

/**
 * 题目:我们把只包含因子2、3、5的数称为丑数。求从小到大顺序第1500个丑数。习惯上把1称为第一个丑数。
 * @author 大闲人柴毛毛
 * @date 2016年3月24日
 */
public class UglyNumber {
	/**
	 * 分析:所谓“只包含因子2、3、5”其实就是只能由2、3、5相乘得到的数称为丑数。
	 * 根据上述特性,丑数的生产过程如下:
	 * 从1开始,分别乘以2、乘以3、乘以5,得到三个新的丑数2、3、5;
	 * 然后再把这三个新的丑数再分别乘以2、乘以3、乘以5,得到9个丑数4、6、10、6、9、15、10、15、25;
	 * 循环上述操作,就能源源不断地生产丑数。
	 * 但我们发现,以上生产过程无法保证丑数按照从小到大的顺序生产,而且生产的丑数中有重复丑数。
	 * 我们只有确保生产的丑数是有序的,才能得到第1500个丑数。因此,在生产的同时,我们需要确保当前生产的丑数都是有序的。
	 * 过程如下:
	 * 假设我们已经生产了n个丑数:1……N,接下来我们要生产第n+1个丑数;
	 * 我们需要从前向后将每个丑数分别乘以2,当找到一个刚刚大于N的丑数时停下;
	 * 然后再从1开始,从前向后将每个丑数乘以3,寻找刚刚大于N的丑数;
	 * 同样的方法将每个丑数乘以5,寻找刚刚大于N的丑数。
	 * 然后选出三个数中最小值,作为第N+1个丑数。
	 * 以此类推,直到计算出1500个丑数为止。
	 * 代码如下:
	 */
	
	/**
	 * 计算第n个丑数
	 * @param n
	 * @return 返回第n个丑数(返回-1表示程序出错)
	 */
	public static int uglyNumber(int n){
		//若n小于0
		if(n<=0){
			System.out.println("n小于1!");
			return -1;
		}
		
		//创建一个长度为n的数组
		int[] a = new int[n];
		a[0] = 1;
		
		//当前丑数个数
		int count = 1;
		
		//循环计算第n个丑数
		while(count<n){
			int i=0,j=0,z=0;
			//从头开始分别乘以2,找到刚刚大于当前最后一个丑数时停下
			for(i=0;i<a.length && a[i]*2<=a[count-1];i++);
			//从头开始分别乘以3,找到刚刚大于当前最后一个丑数时停下
			for(j=0;j<a.length && a[j]*3<=a[count-1];j++);
			//从头开始分别乘以5,找到刚刚大于当前最后一个丑数时停下
			for(z=0;z<a.length && a[z]*5<=a[count-1];z++);
			
			//找出i、j、z的最小值
			int min = a[i]*2;
			if(a[j]*3<min)
				min = a[j]*3;
			if(a[z]*5<min)
				min = a[z]*5;
			
			//将最小值作为第n+1个丑数
			a[count++] = min;
		}
		
		return a[count-1];
	}
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		System.out.println(uglyNumber(5));
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P1019 单词接龙

题目描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙...

3299
来自专栏WD学习记录

牛客网 和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100...

561
来自专栏Deep learning进阶路

OpenCV 学习日记(三)--- 常见数据类型

OpenCV基本数据类型: CvPoint,这些结构中最简单的一个,包含两个整型变量x和y。 CvPoint还有两个兄弟:CvPoint2D32f 和 CvPo...

1950
来自专栏深度学习之tensorflow实战篇

R语言高级绘图命令(标题-颜色等)

plot(x)          以x的元素值为纵坐标、以序号为横坐标绘图 plot(x,y)        x(在x-轴上)与y(在y-轴上)的二元作图 ...

2736
来自专栏海天一树

小朋友学C语言(4):单精度浮点数与双精度浮点数

上节课 简单介绍了浮点数。计算机程序中的浮点数分为单精度浮点数和双精度浮点数。 单精度和双精度精确的范围不一样。 计算机里的最基本的存储单位用位(bit)来表...

32712
来自专栏ml

将多张图片无缝拼接方法

   Qt开发,最近在进行大图片处理实验,开了一个脑洞,试着将大图片切碎,将每一个碎块封装到QImage中作为一个对象,然后将其打包 成一个二维数组,类似于go...

5867
来自专栏机器学习原理

深度学习(1)——tensorflow简介什么是TensorFlow?什么是数据流图?安装基本概念示例变量的更新操作

1723
来自专栏生信宝典

R语言学习 - 散点图绘制

散点图 散点图在生物信息分析中是应用比较广的一个图,常见的差异基因火山图、功能富集分析泡泡图、相关性分析散点图、抖动图、PCA样品分类图(后续推出)等。凡是想展...

2097
来自专栏张俊红

Python数据可视化——matplotlib使用

总第57篇 01|Figure和Subplot: matplotlib的图像都位于figure对象中,相当于一块画布。figure的属性figsize是用来设置...

3235
来自专栏小樱的经验随笔

约瑟夫问题方法总结

n个人围成一个圈,每个人分别标注为1、2、...、n,要求从1号从1开始报数,报到k的人出圈,接着下一个人又从1开始报数,如此循环,直到只剩最后一个人时,该人即...

3088

扫描关注云+社区