剑指offer编程题—丑数

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

求解思路
从题意可以知道，一个丑数的质因子只有2，3，5，那么丑数p = 2^x * 3^y * 5^z，不难发现，一个丑数可以由另一个较小的丑数乘以2或3或5得到。举个例子：
初始化下知道一个丑数1，将1开始乘以2,3,5，就得到2,3,5三个丑数，在从这三个丑数出发乘以2,3,5就得到4，6,10,6，9,15,10,15,25九个丑数，但是会发现由很多重复的丑数，因此需要维持一个set容器（容器内的元素默认按照升序排序，且不会有重复元素）来存储计算出来的丑数。每次取出set容器内的最小元素，将其依次乘以2，3，5，并将3个结果插入set容器。如此反复，直到从容器内弹出元素的个数为index-1，则此时set容器内第一个元素就是答案。
解题步骤：

1. 初始化set容器和count计数器；
2. 只要count小于index，就不断取出set中的最小丑数，并将当前最小丑数依次乘以2，3，5的结果插入set容器，计数器加1；
3. 当count等于index时，跳出while循环，答案就是set容器中的第一个元素。

C++代码：

/*题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，
因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
*/
#include<iostream>
#include<set>
using namespace std;


/*题解思路
从题意可以知道，一个丑数的质因子只有2，3，5，那么丑数p = 2^x * 3^y * 5^z，不难
发现，一个丑数可以由另一个较小的丑数乘以2或3或5得到。举个例子：
初始化下知道一个丑数1，将1开始乘以2,3,5，就得到2,3,5三个丑数，在从这三个丑数出发乘
以2,3,5就得到4，6,10,6，9,15,10,15,25九个丑数，但是会发现由很多重复的丑数，因此需要
维持一个set容器（容器内的元素默认按照升序排序，且不会有重复元素）来存储计算出来的丑数。
每次取出set容器内的最小元素，将其依次乘以2，3，5，并将3个结果插入set容器。如此反复，
直到从容器内弹出元素的个数为index-1，则此时set容器内第一个元素就是答案。
解题步骤：
1. 初始化set容器和count计数器；
2. 只要count小于index，就不断取出set中的最小丑数，并将当前最小丑数依次乘以2，3，5的结果插入set容器，计数器加1；
3. 当count等于index时，跳出while循环，答案就是set容器中的第一个元素。
*/
class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<7) return index; //当1<=index<=6时，第index个丑数就是index自身
        set<long long> st;
        st.insert(1);
        int count=1;
        long long un;
        while(count<index){ 
            un=*(st.begin());
            st.erase(st.begin());
            st.insert(un*2);
            st.insert(un*3);
            st.insert(un*5);
            ++count;
        }
        return *(st.begin());
    }
};

int main(int argc,char **argv)
{
    Solution sol;
    int r=sol.GetUglyNumber_Solution(1500); //输出结果859963392
    cout<<r<<endl;
    return 0;
}