劍指offer程式設計題（JAVA實作)——第33題：醜數

github	https://github.com/JasonZhangCauc/JZOffer

• 劍指offer程式設計題（JAVA實作)——第33題：醜數
• 題目描述
• 把隻包含質因子2、3和5的數稱作醜數（Ugly Number）。
• 例如6、8都是醜數，但14不是，因為它包含質因子7。
• 習慣上我們把1當做是第一個醜數。求按從小到大的順序的第N個醜數。

public class Test33 {

	public static void main(String[] args) {
		System.out.println(GetUglyNumber_Solution(5));

	}

	public static int GetUglyNumber_Solution(int index) {
		if (index < 1) {
			return 0;
		}
		int count = 0;
		int[] array = new int[index];
		int a2 = 0;
		int a3 = 0;
		int a5 = 0;
		array[0] = 1;
		int tmp = 0;
		while (count < index - 1) {
			tmp = min(array[a2] * 2, array[a3] * 3, array[a5] * 5);
			if (tmp == array[a2] * 2)
				a2++;
			if (tmp == array[a3] * 3)
				a3++;
			if (tmp == array[a5] * 5)
				a5++;
			array[++count] = tmp;

		}
		return array[index - 1];
	}

	private static int min(int i, int j, int k) {
		if (i <= j && i <= k) {
			return i;
		} else if (j <= k) {
			return j;
		}
		return k;
	}
}
//複雜度較高
/*	public static int GetUglyNumber_Solution(int index) {
		if (index < 1) {
			return 0;
		}
		int[] array = new int[index + 1];
		array[0] = 1;
		if (index == 1) {
			return array[0];
		}
		int count = 1;
		int i = 2;
		while (count <= index - 1) {
			int tmp = i;

			while (i % 2 == 0) {
				i /= 2;
			}
			while (i % 5 == 0) {
				i /= 5;
			}
			while (i % 3 == 0) {
				i /= 3;
			}
			if (i == 1) {
				array[count] = tmp;
				count++;
			}
			i = tmp + 1;
		}

		return array[count - 1];
	}
}*/