题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解答
暴力枚举会超时。根据丑数的定义，丑数一定是比它小的丑数乘2、3、5得到的。
维护一个数组nums[]，按照递增序列存储着已得到的丑数。已有丑数乘2、3、5得到的最小的超过已有最大丑数即为要找的下一个丑数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public int GetUglyNumber_Solution(int index) {
if (index <= 0) {
return 0;
}
int[] nums = new int[index];
nums[0] = 1;
int curMax = 1, s2 = 0, s3 = 0, s5 = 0;
for (int i = 1; i < index; i++) {
int t2, t3, t5;
for (; nums[s2] * 2 <= curMax; s2++) {
}
t2 = nums[s2] * 2;
for (; nums[s3] * 3 <= curMax; s3++) {
}
t3 = nums[s3] * 3;
for (; nums[s5] * 5 <= curMax; s5++) {
}
t5 = nums[s5] * 5;
nums[i] = Math.min(Math.min(t2, t3), t5);
curMax = nums[i];
}
return nums[index - 1];
}
|