leetcode:ugly Number II

Write a program to find the 

n

-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 

2, 3, 5

. For example, 

1, 2, 3, 4, 5, 6, 8, 9, 10, 12

 is the sequence of the first 

10

 ugly numbers.

Note that 

1

 is typically treated as an ugly number

题目分析：

对于本题，思路应该是丑数肯定是之前的丑数诚意2，3，5得到，但是，怎么样把他们按照顺序排列，我们想可以把丑数分为3类t2,t3,t5,t2,记录的是丑数*2要大于当前所有数小于之后所有数的丑数位置，t3,t5同理，之后从这3个数中选一个最小的作为当前值，选好之后，更新t2,t3,t5。

代码如下：

public static int nthUglyNumber(int n) {
		if (n < 1)
			return 0;
		if (n == 1)
			return 1;
		int[] res = new int[n];
		if (n < 0)
			return 0;
		int t2 = 0;
		int t3 = 0;
		int t5 = 0;
		res[0] = 1;
		int i = 1;
		while (i < n) {
			int x = res[t2] * 2;
			int y = res[t3] * 3;
			int z = res[t5] * 5;
			res[i] = mymin(x, y, z);
			if (res[i] == x) {
				t2++;
			}
			if (res[i] == y) {
				t3++;
			}
			if (res[i] == z) {
				t5++;
			}
			i++;
		}
		return res[n - 1];

	}

	public static int mymin(int a, int b, int c) {
		if (a <= b && a <= c) {
			return a;
		} else if (b <= a && b <= c) {
			return b;
		} else
			return c;

	}