如何优化求解LeetCode Ugly Number II的多重while循环算法？

超时原因分析 #

你现在的实现属于暴力枚举法，存在两个核心性能瓶颈：

• 每个数字都要逐次除以2、3、5做丑数校验，单个数校验的时间复杂度为O(log num)
• 丑数的分布随数值增大越来越稀疏，比如第1690个丑数已经达到2123366400，中间要遍历上千万个非丑数做无效校验，n越大耗时上升越快，自然会触发超时。

优化方案：动态规划三指针法 #

核心思路 #

丑数的生成规律为：所有丑数都可以由更小的丑数分别乘以2、3、5得到。我们不需要遍历所有正整数，直接按从小到大的顺序生成丑数即可，完全规避无效校验：

• 维护一个dp数组，dp[i]代表第i+1个丑数（下标从0开始）
• 维护三个指针p2、p3、p5，分别代表下一个要乘以2、3、5的丑数在dp数组中的位置
• 每次取dp[p2]*2、dp[p3]*3、dp[p5]*5三个值的最小值作为下一个丑数，然后把对应值的指针往后挪一位（如果多个值相等，多个指针都要后移，避免生成重复丑数）

优化后的Java代码 #

class Solution {
    public int nthUglyNumber(int n) {
        // dp数组存储按序生成的丑数
        int[] dp = new int[n];
        // 第一个丑数固定为1
        dp[0] = 1;
        // 三个指针初始都指向第一个丑数
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; i++) {
            // 计算三个候选丑数
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            // 取最小值作为下一个丑数
            dp[i] = Math.min(Math.min(num2, num3), num5);
            // 匹配到的指针后移，避免重复生成
            if (dp[i] == num2) p2++;
            if (dp[i] == num3) p3++;
            if (dp[i] == num5) p5++;
        }
        // 第n个丑数对应数组下标n-1
        return dp[n - 1];
    }
}

效果说明 #

该方法时间复杂度为O(n)、空间复杂度为O(n)，完全避免了非丑数的无效遍历，就算是题目要求的n最大1690的场景，也能在毫秒级完成运算，不会出现超时问题。

内容的提问来源于stack exchange，提问作者kristya-