264. Ugly Number II 264. Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:  

1. 1 is typically treated as an ugly number.
2. n does not exceed 1690.

---

本题是LeetCode Ugly Number的升级版，题目还是不错的，要求出第n个丑数是什么。非常naive的方法就是从1开始不断调用LeetCode Ugly Number中判断丑数的函数，如果是丑数，cnt++，直到cnt==n时输出第n个丑数，但是hint里指出很多都不是丑数，所以这样很浪费时间。 hint里同时给出了怎样直接生成所有丑数序列的方法，不错。 主要思路是这样的，每个丑数都是更小的丑数乘以2,3或5得到的，所以我们可以维护一个丑数序列，要求更大的丑数时，用更小的丑数乘以2,3,5来得到，但是2,3,5对应的那个小丑数并不是一样的。举个例子，首先丑数序列中只有{1}这个元素，对于2,3,5，初始的时候i2=i3=i5=0，表明2,3,5对应丑数序列中的第0个元素1，此时用1分别乘以2,3,5得到的最小值是2，所以下一个丑数是1*2得到的，那么i2++去对应下一个小丑数，i3和i5对应的下标不变。不断这样产生丑数。 不太好描述，请看代码：

class Solution {
public:
    int nthUglyNumber(int n)
    {
        if (n == 1)
            return 1;
        vector<int> ugly_num = { 1 };
        int i2 = 0, i3 = 0, i5 = 0;
        int next_ugly_num = 0;
        while (ugly_num.size() < n) {
            next_ugly_num = min(min(ugly_num[i2] * 2, ugly_num[i3] * 3), ugly_num[i5] * 5);
            if (next_ugly_num == ugly_num[i2] * 2)
                i2++;
            if (next_ugly_num == ugly_num[i3] * 3)
                i3++;
            if (next_ugly_num == ugly_num[i5] * 5)
                i5++;
            ugly_num.push_back(next_ugly_num);
        }
        return next_ugly_num;
    }
};

代码很简洁，但是要想到这个思路还是有难度的。本代码提交AC，用时16MS。