剣指offer:49.醜数

剣指offer:49.丑数のテーマ:私たちは质の因子の2、3と5の数だけを含むことを丑数(Ugly Number)と呼びます.小さいから大きい順のn番目の丑数を求めます.例:入力:n=10出力:12解釈:1,2,3,4,5,6,8,9,10,12は上位10ブス数である.
解析:ダイナミックプランニング解析(c++):unはブス数を保存する配列であり、a,b,cは3つのポインタであり、ブス数であれば+1に向かう.

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> un(n);//    
        int a, b, c;
        a = b = c = 0;
        un[0] = 1;//     
        for (int i = 1; i < n; ++i) {
            int u1 = un[a] * 2, u2 = un[b] * 3, u3 = un[c] * 5;
            un[i] = min(min(u1, u2), u3);//         

			//    
            if (un[i] == u1) ++a;
            if (un[i] == u2) ++b;
            if (un[i] == u3) ++c;   
        }
        return un[n - 1];
    }
};