leetcode 264: 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的问题；

求ans[i]时，遍历ans[i-1]至ans[1]，

循环ans[j]*2，直到找到大于ans[i-1]且最小的值，

然后从当前位置开始，循环ans[k]*3，找最小值，

然后从当前位置同样处理ans[m]*5；

最后对三者求最小值，作为ans[i]。

注意：

用long long。

 1 class Solution {
 2 public:
 3     int nthUglyNumber(int n) {
 4         vector<long long> ans(n+1,1);
 5         for(int i=2;i<=n;i++)
 6         {
 7             int j=i-1;
 8             long long tmp;
 9             for(;j>=1;j--)
10             {
11                 if(ans[j]*2>ans[i-1])
12                     tmp = ans[j]*2;
13                 else
14                     break;
15             }
16             long long tmp2 = tmp;
17             for(;j>=1;j--)
18             {
19                 if(ans[j]*3>ans[i-1])
20                     tmp2 = ans[j]*3;
21                 else
22                     break;
23             }
24             long long tmp3 = tmp;
25             for(;j>=1;j--)
26             {
27                 if(ans[j]*5>ans[i-1])
28                     tmp3 = ans[j]*5;
29                 else
30                     break;
31             }
32             ans[i] = min(min(tmp,tmp2),tmp3);
33         }
34 
35         //for(int i=1;i<=n;i++)
36         //    cout<<ans[i]<<" ";
37         return ans[n];
38     }
39 };

View Code

------------------------更新--------------------------

发现一个更好的算法：见：http://blog.csdn.net/ironyoung/article/details/49045933

相比于我上面的算法，不必从i-1到0一个一个去试2、3、5，

而是记录一下2、3、5下次开始考虑的起始位置，

以3为例，当前乘以3是最小值，下次就不会是在该位置再乘以3，而应往后考虑；

至于重复值，则过滤；

复杂度O(N*K)