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

相关文章

来自专栏小樱的经验随笔

Humble Numbers(丑数) 超详解!

给定一个素数集合 S = { p[1],p[2],...,p[k] },大于 1 且素因子都属于 S 的数我们成为丑数(Humble Numbers or Ug...

2878
来自专栏Spark学习技巧

CountVectorizer

CountVectorizer 关于文本特征提取,前面一篇文章TF-IDF介绍了HashingTF,本文将再介绍一种Spark MLlib的API CountV...

4397
来自专栏数据结构与算法

7828:最大公约数与最小公倍数

7828:最大公约数与最小公倍数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 两个正整数的最大公约数是G,最小公倍数是...

3948
来自专栏菩提树下的杨过

Flash/Flex学习笔记(19):颜色合成与分解的基本原理

传统的RGB颜色体系中,每一个分量值的范围都是0到255,如果转换为2进制的话最多需要8位(比如:十进制的255变成二进制则为11111111),三个分量加起来...

2058
来自专栏和蔼的张星的图像处理专栏

4. 丑数 II 暴力遍历找规律利用set暴力去重排序。

设计一个算法,找出只含素因子2,3,5 的第 n 小的数。 符合条件的数如:1, 2, 3, 4, 5, 6, 8, 9, 10, 12... 样例 如果...

1041
来自专栏清墨_iOS分享

OpenGLES-04 绘制带颜色的立方体

前面几篇文章都只是绘制了平面图形,接下来我们开始绘制一个真正的3D立方体图形。代码在前一篇文章基础上修改。 绘制立方体之前,我们需要知道这个立方体的各个顶点坐...

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

Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3)(A.B.C,3道暴力题,C可二分求解)

A. Is it rated? time limit per test:2 seconds memory limit per test:256 megabyte...

3477
来自专栏xingoo, 一个梦想做发明家的程序员

回溯法算法框架

回溯法:有通用解题法 之称,可以系统的搜索一个问题的所有解和任一解,是一个既带有系统性,又带有跳跃性的搜索算法。 算法基本思想:   确定解空间后   从开始节...

2586
来自专栏灯塔大数据

每周学点大数据 | No.30前序计数

No.30期 前序计数 Mr. 王:我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍...

3397
来自专栏自学笔记

Data Structure_图图论带权图

交通运输,社交网络,互联网,工作的安排,闹区活动等等都可以用到图论处理。图可以分成两大类,一类是无向图,就是没有方向的,就好像两个人都互相认识一样,有向图就是单...

551

扫码关注云+社区