Description:
Ugly number is a number that only have factors 2, 3 and 5.
Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
Example:
If n=9, return 10.
Link:
http://www.lintcode.com/en/problem/ugly-number-ii/
解題思路：
1：scan方式 O(n)時間
因為ugly number的因子只能是2 3 5所以可以把整個ugly number看作是由2 3 5不斷與原有的ugly number里面每個數(shù)相乘所得到的3個集合的總集（集合最初只有元素1）力奋。
需要有3個index分別代表2 3 5與集合中第幾個數(shù)相乘盆犁。每次求出計算值找最小的一個加入到ugly集合中酥艳，對應(yīng)的index則++。
Tips:
在scan方式中拭卿，注意判斷語句骡湖。
if(add == u2) i2++; if(add == u3) i3++; if(add == u5) i5++;為正確語句。
而
if(add == u2) i2++; else { if(add == u3) i3++; else i5++; }會得出錯誤答案峻厚。
原因是在計算過程中响蕴，可能會出現(xiàn)相同的結(jié)果（并且同時為最小）目木，例如2x3 = 6换途， 與3x2 = 6懊渡。此時需要將兩個index都++刽射，不然根據(jù)下面這部分代碼的邏輯會先將i2++然后下一輪i3++，這樣集合中將會出現(xiàn)2個6剃执。
Time Complexity：
完整代碼：
方法1：
int nthUglyNumber(int n) { vector<int> ugly; ugly.push_back(1); int i2 = 0, i3 = 0, i5= 0; for(int i = 0; i < n; i++) { int u2 = ugly[i2] * 2; int u3 = ugly[i3] * 3; int u5 = ugly[i5] * 5; int add = min(u5, min(u2, u3)); if(add == u2) i2++; if(add == u3) i3++; if(add == u5) i5++; ugly.push_back(add); } return ugly[n-1]; }
