当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-64.寻找第N个丑数

发表于: 2012-01-13   作者:bylijinnan   来源:转载   浏览:
摘要: public class UglyNumber { /** * 64.查找第N个丑数 具体思路可参考 [url] http://zhedahht.blog.163.com/blog/static/2541117420094245366965/[/url] * 题目:我们把只包含因子 2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14


public class UglyNumber {

	/**
	 * 64.查找第N个丑数
具体思路可参考 [url] http://zhedahht.blog.163.com/blog/static/2541117420094245366965/[/url]
	 * 
题目:我们把只包含因子
2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。

	 */
	public static void main(String[] args) {
		UglyNumber un=new UglyNumber();
		int n=50;
		int re=un.findNthUglyNumber2(n);
		System.out.println(re);
	}

	public int findNthUglyNumber1(int n){
		int count=0;
		int i=1;
		while(count<n){
			if(isUglyNumber(i)){
				count++;
				if(count==n){
					return i;
				}
			}
			i++;
		}
		return -1;
	}
	
	public boolean isUglyNumber(int x){
			while(x%2==0)x/=2;
			while(x%3==0)x/=3;
			while(x%5==0)x/=5;
			return x==1?true:false;
	}
	//like finding a SuShu/PrimeNumber
	public int findNthUglyNumber2(int n){
		int re=-1;
		int[] a=new int[n];
		a[0]=1;
		int p2=0,p3=0,p5=0;
		int i=1;
		while(i<n){
			a[i]=min(a[p2]*2,a[p3]*3,a[p5]*5);
			while(a[p2]*2<=a[i])p2++;
			while(a[p3]*3<=a[i])p3++;
			while(a[p5]*5<=a[i])p5++;
			i++;
		}
		re=a[i-1];
		return re;
	}
	public int min(int a,int b,int c){
		return (a<b?a:b)<c?(a<b?a:b):c;
	}
}


java-64.寻找第N个丑数

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
#include <stdio.h> //判断一个数是否为丑数 bool IsChou(__int64 num) { while(num!=0) { if
题目要求:   我们把只包含因子2、3和5的数称为丑数。例如6、8都是丑数,但是14不是,因为它包含
J - Palindrome Numbers Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu Submit
 J - Palindrome Numbers Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu Su
寻找最优的 TopN 算法 1 概要 在大量的数据记录中,依据某可排序的记录属性(一般为数字类型),找
题目描述: 把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它
前言 寻找第K小的数属于顺序统计学范畴,通常我们可以直接在O(NlgN)的时间内找到第K小的数,使用归
8 丑数
题目: 我们把只包含因子 2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为
9 丑数
出自:何海涛的剑指offer #include "stdafx.h" #include <iostream> using namespace std; in
输出第N个素数 public class FindNthPrime { public static void main(String[] args){ int N = Int
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号