首先看K一个难看的数字

首先看K一个难看的数字

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

把仅仅包括质因子2、3和5的数称作丑数(Ugly Number),比如:2,3,4,5,6,8,9,10,12,15,等,习惯上我们把1当做是第一个丑数。


写一个高效算法,返回第n个丑数。

import static java.lang.Math.min;
import static java.lang.System.out;

public class UglyNumber {

	public static void main(String[] args) {
		out.println(findKthUglyNumber(1500));
	}

	/**
	 * 寻找第K个丑数
	 * 
	 * @param k
	 * @return
	 */
	public static int findKthUglyNumber(int k) {
		if (k < 0) {
			return 1;// 把第一个丑数返回
		}
		int[] numbers = new int[k];
		numbers[0] = 1;
		int next = 1;
		int ugly2Index = 0;
		int ugly3Index = 0;
		int ugly5Index = 0;
		while (next < k) {
			int uglyNum = min(numbers[ugly2Index] * 2,
					min(numbers[ugly3Index] * 3, numbers[ugly5Index] * 5));
			numbers[next] = uglyNum;
			while (numbers[ugly2Index] * 2 <= numbers[next]) {
				ugly2Index++;
			}
			while (numbers[ugly3Index] * 3 <= numbers[next]) {
				ugly3Index++;
			}
			while (numbers[ugly5Index] * 5 <= numbers[next]) {
				ugly5Index++;
			}
			next++;
		}
		return numbers[k - 1];// 从0開始
	}

}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117395.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号