21
08/2015
[LeetCode] Ugly Number II
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.
解题思路：
题意说找到第n个Ugly Number。一个naive的办法是验证每个数，直到第n个丑数产生为止。但是这样可能会产生超时错误。
一个比较好的办法就是直接产生丑数，然后计数即可。如何找到下一个丑数呢？这个规律还真不好找。网上查阅了一些资料，才弄懂。
1*2，2*2，3*2，4*2，5*2，6*2，8*2… 1*3，2*3，3*3，4*3，5*3，6*3，8*3… 1*5，2*5，3*5，4*5，5*5，6*5，8*5…
丑数列表可以按上面排列。注意，可能会有重复的，比如3*2和2*3。对于下一个丑数，都是将某个已有丑数乘以2或3或5，每一行都是顺序的丑数*相应的质，因此需要一个数组来记录已经出现过的丑数。将所有丑数分成三组（可能一个丑数分到多个组中 ），记录当前丑数的下标，然后选取下一个最小的丑数即可。注意这里不是else if，因为每个丑数可以分配到多个组中。
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> result(n, 0);
int index2 = 0, index3 = 0, index5 = 0;
result[0] = 1;
for(int i = 1; i < n; i++){
result[i] = min(min(result[index2] * 2, result[index3] * 3), result[index5] * 5);
if(result[i] == result[index2] * 2) index2++;
if(result[i] == result[index3] * 3) index3++;
if(result[i] == result[index5] * 5) index5++;
}
return result[n-1];
}
};转载请注明：康瑞部落 » [LeetCode] Ugly Number II
0 条评论