题目描述

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

样例

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

算法1

(多路归并) $O(n)$

* 如果丑数序列为S:1,2,3,4,5,6,8...
* 则丑数序列可以用{1},S1,S2,S3的并集表示，
* 其中：S1 = S · 2, S2 = S · 3, S3 = S · 5
    S1：1·2，2·2，3·2，4·2，5·2，6·2，8·2 ...
    S2：1·3，2·3，3·3，4·3，5·3，6·3，8·3 ...
    S3：1·5，2·5，3·5，4·5，5·5，6·5，8·5 ...
* 即每个丑数乘上2,3,5，得到的还是丑数
* 从1开始，分别乘上2,3,5这三个因子，得到的最小数就是下一个丑数，且对应的序列指针往后移一位
* 注意：判断是否是最小数不能用else if，可能会出现2·3,3·2相等这种情况，需要两个序列中的指针都往后移一位

Java 代码

class Solution {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        for(int i = 0, j = 0, k = 0, u = 1; u < n; u++){
            int t = Math.min(ugly[i]*2, ugly[j]*3);
            int min = Math.min(t, ugly[k]*5);
            if(min == ugly[i]*2) i++;
            if(min == ugly[j]*3) j++;
            if(min == ugly[k]*5) k++;
            ugly[u] = min;
        }
        return ugly[n-1];
    }
}