CodingInterview-丑数

按照从小到大的顺序生成丑数，主要思路是使用三个指针分别跟踪丑数中需要乘以三个因子的数字的最小数字。然后通过三个循环来移动指针，使其移动到合适的位置（使用三个因子生成的数字都比当前队列中的数字大）。需要注意的是这里需要使用<=而非<，因为第一，需要让当前选中因子的指针+1，第二，还会有通过两个因子计算得到数字是相同的情况。

和书中的例子相比，这段程序使用 deque 双端队列来对内存占用进行优化，使得数组可以根据计算的进度舍去后面没用的地方。优化的效果明显，牛客网 oj 中的内存占用从 624k 下降到了 376k，算法耗时没有显著增加。

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<=0) return 0;
        deque<int> uglyNums;
        uglyNums.push_back(1);
        int next_index=1;
        int index_2=0,index_3=0,index_5=0;
        while(next_index<index){
            uglyNums.push_back(getMin(uglyNums[index_2]*2,uglyNums[index_3]*3,uglyNums[index_5]*5));
            next_index++;
            while(uglyNums[index_2]*2<=uglyNums.back()) index_2++;
            while(uglyNums[index_3]*3<=uglyNums.back()) index_3++;
            while(uglyNums[index_5]*5<=uglyNums.back()) index_5++;
            int popNum=0;
            //优化内存占用
            while(uglyNums.size()>0 && uglyNums[0]*5<=uglyNums.back()){
                popNum++;
                uglyNums.pop_front();
            }
            index_2-=popNum;index_3-=popNum;index_5-=popNum;
        }
        return uglyNums.back();
    }
    int getMin(int num1,int num2,int num3){
        int min=num1;
        if(num2<min) min=num2;
        if(num3<min) min=num3;
        return min;
    }
};