文档章节

【九度OJ1214】|【剑指offer34】丑数

aqia358
 aqia358
发布于 2013/10/16 19:54
字数 734
阅读 167
收藏 1
题目描述:

把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

输入:

输入包括一个整数N(1<=N<=1500)。

输出:

可能有多组测试数据,对于每组数据,
输出第N个丑数。

方法一:(粗糙啊)

import java.util.Scanner;

public class CopyOfMain {

	public boolean isPrime(int number){
		boolean flag = true;
		for(int i = 2; i <= Math.sqrt(number); i++){
			if(number % i == 0){
				flag = false;
				break;
			}
		}
		return flag;
	}
	public boolean isUgly(int number){
		if(isPrime(number)){
			if(number == 2 || number == 3 || number == 5 || number == 1)
				return true;			
			else{
				return false;
			}
		}
		boolean flag = false;
		for(int i = 2; i < Math.sqrt(number) + 1; i++){
			int a = number % i;
			if(a == 0){
				flag = isUgly(i)&&isUgly(number/i);
			}
		}
		return flag;
	}
	public void countUgly(int count){
		if(count <= 6)
			System.out.println(count);
		else{
			int j = 6;
			int number = 7;
			while(j < count){
				if(isUgly(number++)){
					j++;
				}
			}
			System.out.println(number-1);
		}
	}
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		CopyOfMain m = new CopyOfMain();
		m.countUgly(s.nextInt());
	}

}

咋想的呢!硬生生的解,效率极低最后Runtimeout

方法二

import java.util.Scanner;

public class Copy_2_of_Main {

	public boolean isUgly(int number) {
		while (number % 2 == 0)
			number /= 2;
		while (number % 3 == 0)
			number /= 3;
		while (number % 5 == 0)
			number /= 5;
		return number == 1;
	}

	public void countUgly(int count) {
		int j = 0;
		int number = 1;
		while (j < count) {
			if (isUgly(number++)) {
				j++;
			}
		}
		System.out.println(number - 1);
	}

	public static void main(String[] args) {
		// Scanner s = new Scanner(System.in);
		Copy_2_of_Main m = new Copy_2_of_Main();
		// m.countUgly(s.nextInt());
		for (int i = 1; i < 20; i++)
			m.countUgly(i);
	}

}
依然是效率问题会额外计算非丑数。

方法三:(参考http://www.cnblogs.com/mingzi/archive/2009/08/04/1538491.html)

import java.util.Scanner;

public class Main {

	public void countUgly(int count) {
		if(count <= 0)return;
		int[] array = new int[count];
		int pos = 0;
		array[0] = 1;
		int i = 0;
		int j = 0;
		int k = 0;
		while (pos < count - 1) {
			while (array[pos] >= array[i] * 2)
				i++;
			while (array[pos] >= array[j] * 3)
				j++;
			while (array[pos] >= array[k] * 5)
				k++;
			array[++pos] = Min(array[i] * 2, array[j] * 3, array[k] * 5);
		}
		System.out.println(array[pos]);
	}

	public int Min(int a, int b, int c) {
		a = Math.min(a, b);
		return Math.min(a, c);
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		Main m = new Main();
		while(s.hasNext())
			m.countUgly(s.nextInt());
	}

}
    试图只计算丑数,而不在非丑数的整数上花费时间。根据丑数的定义,丑数应该是另一个丑数乘以 2 3 或者 5 的结果( 1 除外)。因此我们可以创建一个数组,里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以 2 3 或者 5 得到的。在已知一个数组大小的丑数序列时,下一个丑数必然大于已知的最大丑数,并且该丑数是由已知数组里的丑数 乘以 2 3 或者 5 的结果。因此我们可以先找到已知数组里的丑数乘以2、3、5得到的第一个大于已知最大丑数的值,然后比较这三个值,最小的那个即为要求得的丑数。

    这种算法不需要在非丑数的整数上做任何计算,因此时间复杂度要低很多。


© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 82
码字总数 30297
作品 0
海淀
程序员
私信 提问
数据结构与算法(4)——优先队列和堆

前言:题图无关,接下来开始简单学习学习优先队列和堆的相关数据结构的知识; 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)—...

我没有三颗心脏
2018/07/12
0
0
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
2018/06/03
0
0
5位大咖同台论道,中西方微服务有何异同?(附PPT下载)

11月4日数人云与微软联合主办的 《论道云原生和微服务 剑指何方》在北京顺利举行 来自微软、数人云、EasyStack的五位技术大牛分别进行了分享,其中更有从美国赶来的微软Azure云容器技术的首席...

数人云
2017/11/07
0
0
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴
2017/11/08
0
0
LeetCode:Super Ugly Number - 超级丑数

1、题目名称 Super Ugly Number(超级丑数) 2、题目地址 https://leetcode.com/problems/super-ugly-number/ 3、题目内容 英文: Write a program to find the nth super ugly number. Sup......

北风其凉
2015/12/19
2.8K
2

没有更多内容

加载失败,请刷新页面

加载更多

mysql grant 用户权限总结

用户权限管理主要有以下作用: 1. 可以限制用户访问哪些库、哪些表 2. 可以限制用户对哪些表执行SELECT、CREATE、DELETE、DELETE、ALTER等操作 3. 可以限制用户登录的IP或域名 4. 可以限制用...

Airship
33分钟前
1
0
RabbitMQ学习(3)

1. 消费端 1. 消费端通过推模式或者拉模式从RabbitMQ中获取并消费消息,当消费者确认处理消息后,可以手动确认消息已被接收,然后就会将该消息从RabbitMQ的队列中标记再清除,消费者端还可以...

江左煤郎
44分钟前
1
0
linux mysql(5.7)开启慢查询

一、有3个配置需要设置, 1:相关开关 2:日志目录文件 3:慢查询的时间限制 二、设置完之后重启mysql service mariadb restart 三、重启后做个测试 连接mysql 并查询: select sleep(6); 四...

chro008
51分钟前
2
0
选择IDC机房、选择硬件、上架服务器、装系统

选择IDC机房 当业务量比较大的时候,往往选用IDC而不是公有云来跑业务。 IDC机房的服务一般分为两种 需要我们自己购买服务器和网络设备,托管到IDC机房。IDC机房会提供布线、巡检、硬件操作等...

李超小牛子
53分钟前
2
0
《傲慢与偏见》的读书笔记与读后感作文2400字

《傲慢与偏见》的读书笔记与读后感作文2400字: 作者:孙苑馨;笔者按:读书这个习惯是我爸妈养出来的。小时候父母赚的钱除了吃饭穿衣剩下的就是买书了,他们除了买各种新鲜出版的文艺派图书...

原创小博客
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部