剑指 Offer 49. 丑数 (opens new window)

1.三指针+动态规划

分析：解题核心在于挖掘丑数之间的关联与转换关系，一个丑数必定是由另一个丑数乘上2、3、5得到的。如果仅仅通过枚举的方式来找丑数的话，时间复杂度O(dp[n-1])。采用动规数组保存子问题的解。

接下来难点在于求第i个丑数dp[i]时，如何找到“另一个丑数”：

• 最直观的方法就是通过枚举dp[0]到dp[i-1]的每个丑数，每个数都分别乘上2、3、5，然后取大于dp[i-1]的最小丑数作为dp[i-1]
• 进一步思考优化，利用dp数组的有序性。假设dp[i]是由dp[k]乘3得到，那么下次求解dp[i+1]时就不需要考虑dp[0]到dp[k]乘3的结果了，因为它们肯定小于等于dp[i]。
• 再进一步思考，乘3的指针已经确定了，那乘2和5的指针呢，打个比方2x5<4x3，因此三种计算规则的指针不能是同步的。
• 到这里思路就很清晰了，分三个指针，每次取三个指针对应位置的丑数乘上对应的计算规则数的最小值，更新到dp[i]。

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp=new int[n];
        dp[0]=1;
        int a=0,b=0,c=0;
        for(int i=1;i<n;i++){
            dp[i]=Math.min(dp[a]*2,Math.min(dp[b]*3,dp[c]*5));
            if(dp[a]*2==dp[i]) a++;
            if(dp[b]*3==dp[i]) b++;
            if(dp[c]*5==dp[i]) c++;
        }
        return dp[n-1];
    }
}