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

相关文章

来自专栏编程直播室

读书笔记:《算法图解》第三章 递归

1415
来自专栏移动开发面面观

排序备忘

排序是算法的一项基础能力,也是面试必考题。如何写一个恰当的排序,也是一个软件工程师的基本必备技能。

461
来自专栏JMCui

学习思考之《编程之美》.

一、智者说:无聊的时候来几道算法题,可以训练训练自己的思维嘛!难怪之前人家说数学好的人编程起来事半功倍,写算法的过程中真是深有体会啊!感觉就像是在做大学的高数题...

2909
来自专栏杨建荣的学习笔记

Python实现工厂模式的两个例子

设计模式在Java里面这个是必须的中高阶内容。而很少看到Python里面刻意去讲这个,关于Python实现的设计模式,一直以来是自己比较好奇而且想深入学习的一个...

3204
来自专栏章鱼的慢慢技术路

牛客网2018年全国多校算法寒假训练营练习比赛(第二场)

2394
来自专栏绿巨人专栏

函数式编程 : 一个程序猿进化的故事

3399
来自专栏WOLFRAM

用 Wolfram 语言来做2017年高考数学试题之天津理科卷

1484
来自专栏aCloudDeveloper

经典排序之 快速排序

Author: bakari  Date: 2012.7.21 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之...

18010
来自专栏有趣的Python

c++实战-(一)-走出迷宫

走出迷宫 走出规则: 左手规则 & 右手规则 原则:保证手始终触墙 结果:走出迷宫 情况1:有入有出。(特殊情况,出入口是一个) ? 架构描述: 迷宫类(Maz...

2794
来自专栏落影的专栏

程序员进阶之算法练习(二十三)

前言 趁着8月还没结束,更新一篇算法练习。 正文 1. Alyona and mex 题目链接 题目大意: mex()定义:mex(arr)是 数组arr的...

3927

扫码关注云+社区