丑数

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解题思路

安排3个队列分别存放 ×2、×3、×5的数，为什么这么做？因为我们需要每次从三个队列中的头部取出其中最小的值，然后将这个值再分别×2、×3、×5存放到那三个队列的尾部，这会使得这三个队列是有序的（从小到大）。
初始化：
q_2 = [1, ]
q_3 = [1, ]
q_5 = [1, ]
第一轮：
res = 1 (将三个队列的头部为1的都弹出)
q_2 = [1×2, ]
q_3 = [1×3, ]
q_5 = [1×5, ]
第二轮：
res = 2 (将三个队列的头部为2的都弹出)
q_2 = [2×2, ]
q_3 = [1×3, 2×3, ]
q_5 = [1×5, 2×5, ]
第三轮：
res = 3 (将三个队列的头部为3的都弹出)
q_2 = [2×2, 3×2, ]
q_3 = [2×3, 3×3, ]
q_5 = [1×5, 2×5, 3×5, ]
......

class Solution {
public:
    int GetUglyNumber_Solution(int index) {

        queue<int> q_2,q_3,q_5;
        int res=0;    //index=0时，需要返回0

        //初始化，将 1 push 到3个对列里
        q_2.push(1);
        q_3.push(1);
        q_5.push(1);

        for(int i=0;i<index;i++)
        {
            //选取三个队列头部最小的值
            res = min(q_2.front(),min(q_3.front(),q_5.front()));

            //分别将res ×2, ×3, ×5 放到三个队列中
            q_2.push(res*2);
            q_3.push(res*3);
            q_5.push(res*5);

            //弹出三个队列的头部为res的数
            if(q_2.front()==res)
                q_2.pop();
            if(q_3.front()==res)
                q_3.pop();
            if(q_5.front()==res)
                q_5.pop();

        }
        return res;
    }
};