题解 | #丑数#

#include <vector>
class Solution {
public:


    int GetUglyNumber_Solution(int index) {
       if(!index) return 0;
      
       //只包含质因数为2、3、5的数，求第n个丑数 
       //逆向思维
       
       vector<int> ans(index + 2);
       int f1 = 1, f2  = 1, f3 = 1;
       ans[1] =  1;
       for(int i = 2; i <= index; i++){
          ans[i] = min(ans[f1] * 2, min(ans[f2] * 3, ans[f3] * 5));
          if(ans[f1] * 2 == ans[i]) f1++;
          if(ans[f2] * 3 == ans[i]) f2++;
          if(ans[f3] * 5 == ans[i]) f3++;
       }
       return ans[index];
    }
};