剑指 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 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

聊聊NettyConnector的start及shutdown

reactor-netty-0.7.6.RELEASE-sources.jar!/reactor/ipc/netty/NettyConnector.java

841
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

2667
来自专栏跟着阿笨一起玩NET

c#实现打印功能

2612
来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

2496
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5257
来自专栏hbbliyong

WPF Trigger for IsSelected in a DataTemplate for ListBox items

<DataTemplate DataType="{x:Type vm:HeaderSlugViewModel}"> <vw:HeaderSlug...

4054
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

2605
来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

3035
来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

2102
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

4798

扫码关注云+社区