First, look at K, an ugly number

Hello everyone , I meet you again , I'm the king of the whole stack .

Include only qualitative factors 2、3 and 5 The number of is called ugly （Ugly Number）, such as ：2,3,4,5,6,8,9,10,12,15, etc. , It's customary for us to 1 As the first ugly number . Write an efficient algorithm , Back to page n Ugly number .

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));
	}

	/**
	 *  Search for the first K Ugly number 
	 * 
	 * @param k
	 * @return
	 */
	public static int findKthUglyNumber(int k) {
		if (k < 0) {
			return 1;//  Return the first ugly number 
		}
		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];//  from 0 Start 
	}

}

Copy

Copyright notice ： This article is an original blog article , Blog , Without consent , Shall not be reproduced .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/117395.html Link to the original text ：https://javaforall.cn