264. 丑数2

一、题目描述

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

提示：

• 1 <= n <= 1690

二、解题思路

丑数是只包含 2、3、5 这 3 个质因素的数。

• 后面的丑数肯定是由前面的丑数计算得来的
• 后面的丑数 = min(前面的丑数 * 2/3/5)

前面所有的丑数，分别乘以 2/3/5，去重后，它们中的最小积就是下一个丑数。

比如说，前面的丑数列表是这样的：

[1, 2, 3, 4, 5]

那么分别乘以 2/3/5 后，得到结果是：

// 乘以2
[2, 4, 6, 8, 10]

// 乘以3
[3, 6, 9, 12, 15]

// 乘以5
[5, 10, 15, 20, 25]

去掉之前的 [1, 2, 3, 4, 5]，这里面最小的就是 6，所以下一个丑数就是 6。

但是这种方式会有很多重复计算，比如前面出现过的 [2, 3, 5]，每次都要算一遍。

我们可以从比最后一个丑数大的位置开始，比如丑数列表是：

[1, 2, 3, 4, 5, 6, 8, 10]

那么对于 2/3/5 这几种情况：

• 10 / 2 = 5，那么 2 可以从比 5 大的值开始计算，对应列表里的 6
• 10 / 3 = 3，那么 3 可以从比 3 大的值开始计算，对应列表里的 4
• 10 / 5 = 2，那么 5 可以从比 2 大的值开始计算，对应列表里的 3

那么它们下一个列表是：

// 乘以2，从 6 开始
[12, 16, 20]

// 乘以3，从 4 开始
[12, 15, 18, 24, 30]

// 乘以5，从 3 开始
[15, 20, 25, 30, 35]

前面的重复值没有了，但还是有很多不必要的计算，比如后面的 [16, 18, 20] 这些。

• 反正是求最小值，只需要乘以 2、乘以 3、乘以 5 的第一个值就可以了

所以上面实际上只需要 3 个数就够了：

• 12 (6 * 2)
• 12 (4 * 3)
• 15 (3 * 5)

这三个数中的最小值 12 就是下一个丑数。

那怎么快速找到 2 、3、5 的起始位置呢？

• 可以用 3 个指针分别记录 2、3、5 下一次的起始位置

比如这次 3 个指针指向的元素是 [6, 4, 3]：

• 起始元素分别乘以 2、3、5 得到 [12, 12, 15]，最小值 12 就是下一个丑数
• 最后更新指针，往后移动 1 位 [8, 5, 3]（因为 2、3 的值相同，所以都移动了）

通过 3 指针的方式，可以避免计算前面无用的重复值，也能快速地算出下一个丑数。

三、复杂度分析

• 时间：O(n)
• 空间：O(n)

四、参考代码

/**
 * 思路：3指针，分别指向2、3、5的下一个起始位置，下一个丑数肯定是从这 3 个数里面出来的
 * <p>
 * 复杂度：时间 O(n) 空间 O(n)
 * <p>
 * 执行耗时:2 ms,击败了97.22% 的Java用户
 * 内存消耗:40.9 MB,击败了36.82% 的Java用户
 */
private int nthUglyNumber(int n) {
    int[] nums = new int[n];
    nums[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;
    for (int i = 1; i < n; ) {
        // 下一个丑数
        int next2 = nums[p2] * 2;
        int next3 = nums[p3] * 3;
        int next5 = nums[p5] * 5;
        int next = Math.min(next2, Math.min(next3, next5));

        // 不用 else 是为了去掉重复的数字
        if (next == next2) {
            p2++;
        }
        if (next == next3) {
            p3++;
        }
        if (next == next5) {
            p5++;
        }

        nums[i++] = next;
    }
    return nums[n - 1];
}