题解 | #丑数#

一、维护两个序列，分别叫uglys和factors

uglys表示生成的丑数序列，每时刻该序列都是正确的，无需调整，初始化值只有1

factors与uglys对应，每个元素表示对应丑数当前应该乘的因子（只可能是2、3、5和-1），初始值2

二、丑数生成过程，循环执行下面的步骤

1. 从factors中找到非-1的因子乘以对应的uglys元素，得到乘积序列A，
2. 在A中找到一个最小值min，如果不等于uglys最后一个元素,则添加到uglys的最后，起名lastUgly，更新lastUgly对应的factors元素为2
3. 将min对应的factors元素更新为下一值。2的下一值为3，3的下一值为5，5的下一值为-1 提示：如果想节省空间，则序列可以采用list，因子更新为-1时,对应的两个list都可以删除元素。

class Solution {
public:
    Solution() : base(6)
    {
        base[0] = 2;
        base[2] = 3;
        base[3] = 5;
        base[5] = -1;
    }
    
    int GetUglyNumber_Solution(int index) {

        if (index <= 0)
        {
            return 0;
        }
                
        vector<int> uglys, factors;        
        uglys.push_back(1);
        factors.push_back(2);
        int start = 0;
        while (uglys.size() != index)
        {
            int min = uglys[start] * factors[start];
            int minIndex = start;
            for (int i = start + 1; i < uglys.size(); i++)
            {
                int multiResult = uglys[i] * factors[i];
                if (multiResult < min)
                {
                    min = multiResult;
                    minIndex = i;
                }
            }

            if (min > uglys[uglys.size() - 1])
            {
                uglys.push_back(min);
                factors.push_back(2);
            }

            factors[minIndex] = base[factors[minIndex]];
            if (factors[minIndex] == -1)
            {
                start++;
            }
        }

        return uglys[uglys.size() - 1];
    }
    
private:
    vector<int> base;

};